Submission #65874953

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct BIT {
    int n;
    vector<ll> t;
    BIT(int _n): n(_n), t(n+1,0) {}
    void add(int i, ll v){ for(; i<=n; i+=i&-i) t[i]+=v; }
    ll sum(int i){ ll s=0; for(; i>0; i-=i&-i) s+=t[i]; return s; }
    ll sum(int l, int r){ return sum(r) - sum(l-1); }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin>>N;
    vector<vector<pair<int,int>>> g(N+1);
    vector<int> U(N), V(N), child(N);
    for(int i=1;i<N;i++){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BIT {
    int n;
    vector<ll> t;
    BIT(int _n): n(_n), t(n+1,0) {}
    void add(int i, ll v){ for(; i<=n; i+=i&-i) t[i]+=v; }
    ll sum(int i){ ll s=0; for(; i>0; i-=i&-i) s+=t[i]; return s; }
    ll sum(int l, int r){ return sum(r) - sum(l-1); }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin>>N;
    vector<vector<pair<int,int>>> g(N+1);
    vector<int> U(N), V(N), child(N);
    for(int i=1;i<N;i++){
        cin>>U[i]>>V[i];
        g[U[i]].push_back({V[i],i});
        g[V[i]].push_back({U[i],i});
    }

    vector<int> tin(N+1), tout(N+1), parent(N+1);
    int timer = 0;
    function<void(int,int)> dfs = [&](int u, int p){
        tin[u]=++timer;
        parent[u]=p;
        for(auto [v, idx]: g[u]){
            if(v==p) continue;
            dfs(v,u);
            child[idx] = v;
        }
        tout[u]=timer;
    };
    
    dfs(1,0);
    
    BIT bit(N);
    for(int i=1;i<=N;i++){
        bit.add(tin[i],1);
    }
    ll total = N;
    int Q; cin>>Q;
    while(Q--){
        int type; cin>>type;
        if(type==1){
            int x; ll w;
            cin>>x>>w;
            bit.add(tin[x], w);
            total += w;
        } else {
            int y; cin>>y;
            int c = child[y];
            ll s = bit.sum(tin[c], tout[c]);
            ll t = total - s;
            cout << llabs(s - t) << "\n";
        }
    }
    return 0;
}

Submission Info

Judge Result