Submission #65917991

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
import sys
sys.setrecursionlimit(10**6)
n=int(input())
g=[[]for _ in range(n)]
edges=[0]*n
for i in range(1,n):
    u,v=map(int,input().split())
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)
    edges[i]=(u,v)
tin=[0]*n
tout=[0]*n
parent=[0]*n
timer=0
def dfs(u,p):
    global timer
    tin[u]=timer
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

/*
import sys
sys.setrecursionlimit(10**6)
n=int(input())
g=[[]for _ in range(n)]
edges=[0]*n
for i in range(1,n):
    u,v=map(int,input().split())
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)
    edges[i]=(u,v)

tin=[0]*n
tout=[0]*n
parent=[0]*n
timer=0
def dfs(u,p):
    global timer
    tin[u]=timer
    timer+=1
    parent[u]=p
    for v in g[u]:
        if v==p:continue
        dfs(v,u)
    tout[u]=timer-1
dfs(0,-1)
child=[0]*n
for i in range(1,n):
    u,v=edges[i]
    child[i]=u if parent[u]==v else v

from atcoder.fenwicktree import FenwickTree
ft=FenwickTree(n)
for i in range(n):
    ft.add(tin[i],1)
for _ in range(int(input())):
    q=list(map(int,input().split()))
    if q[0]==1:
        x=q[1]-1
        w=q[2]
        ft.add(tin[x],w)
    else:
        y=q[1]
        v=child[y]
        s=ft.sum(tin[v],tout[v]+1)
        ans=abs(ft.sum(0,n)-2*s)
        print(ans)
*/

#include <bits/stdc++.h>
#include <atcoder/fenwicktree>
using namespace std;
using namespace atcoder;

int n;
vector<vector<int>> g;
vector<pair<int,int>> edges;
vector<int> tin, tout, parent, child;
int timer = 0;

void dfs(int u, int p) {
    tin[u] = timer++;
    parent[u] = p;
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
    tout[u] = timer - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    g.resize(n);
    edges.resize(n);
    tin.resize(n);
    tout.resize(n);
    parent.resize(n);
    child.resize(n);

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
        edges[i] = {u, v};
    }

    dfs(0, -1);

    for (int i = 1; i < n; ++i) {
        int u = edges[i].first, v = edges[i].second;
        child[i] = (parent[u] == v) ? u : v;
    }

    fenwick_tree<long long> ft(n);
    for (int i = 0; i < n; ++i) {
        ft.add(tin[i], 1);
    }

    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x, w;
            cin >> x >> w;
            --x;
            ft.add(tin[x], w);
        } else {
            int y;
            cin >> y;
            int v = child[y];
            long long s = ft.sum(tin[v], tout[v] + 1);
            long long total = ft.sum(0, n);
            cout << abs(total - 2 * s) << '\n';
        }
    }

    return 0;
}

Submission Info

Judge Result