Submission #65907423

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef _Alignof
#define _Alignof __alignof__
#endif
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
#define yes "Yes"
#define no "No"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
const vector<char> alpha = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
int dx[4] = {0, 1, 0, -1};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ifndef _Alignof
#define _Alignof __alignof__
#endif
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
#define yes "Yes"
#define no "No"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
const vector<char> alpha = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
const ll INF = 1e9 + 7;
const ll MOD = 998244353;
template <typename T> bool chmax(T &a, T b) {if (a < b) {a = b;return true;}return false;}
template <typename T> bool chmin(T &a, T b) {if (a > b) {a = b;return true;}return false;}
vector<char> q={'v','>','^','<'};

int main(){
    int N;
    cin >> N;
    vector<pair<int,int>> edges(N-1);
    vvi adj(N);
    REP(i, N-1){
        int u, v;
        cin >> u >> v;
        --u; --v;
        edges[i] = {u, v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> par(N, -1), tin(N), tout(N);
    int timer = 0;
    stack<pair<int,int>> st;
    st.push({0, 0});
    par[0] = -1;

    while(!st.empty()){
        int v = st.top().first;
        int &i = st.top().second;
        if (i == 0) {
            tin[v] = ++timer;
        }
        if (i < (int)adj[v].size()){
            int u = adj[v][i++];
            if (u == par[v]) continue;
            par[u] = v;
            st.push({u, 0});
        } else {
            tout[v] = timer;
            st.pop();
        }
    }

    vector<int> child(N-1);
    REP(i, N-1){
        int u = edges[i].first, v = edges[i].second;
        if (par[v] == u) child[i] = v;
        else child[i] = u;
    }

    vector<ll> bit(N+1, 0);
    auto add = [&](int i, ll v){
        for (; i <= N; i += i & -i) bit[i] += v;
    };
    auto sum = [&](int i){
        ll s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    };
    auto range_sum = [&](int l, int r){
        return sum(r) - sum(l-1);
    };

    REP(v, N) add(tin[v], 1);
    ll total = N;

    int Q;
    cin >> Q;
    while (Q--){
        int t;
        cin >> t;
        if (t == 1){
            int x; ll w;
            cin >> x >> w;
            --x;
            add(tin[x], w);
            total += w;
        } else {
            int y;
            cin >> y;
            --y;
            int v = child[y];
            ll s = range_sum(tin[v], tout[v]);
            ll diff = total - 2*s;
            if (diff < 0) diff = -diff;
            cout << diff << endl;
        }
    }
}

Submission Info

Judge Result