This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
if (heavy[u] == -1)
return;
build_hld(u, heavy[u], r);
for (int v : adj[u]) {
if (v == p || v == heavy[u]) continue;
build_hld(u, v, v);
}
}
/*
void build_hld(int s) {
pos[s]=Tm;
flat[Tm]=s;
++Tm;
trav(u, adj[s]) if(u!=par[s]) {
if(u==adj[s][0])
anc[u]=anc[s];
else
anc[u]=u;
build_hld(u);
}
}*/
//segment tree
int st[maxn];
bool __[maxn];
#define tm ((tl+tr)/2)
#define lv (2*v+1)
#define rv (2*v+2)
void build_st(int v, int tl, int tr) {
if(tl==tr)
st[v]=flat[tl];
else {
build_st(lv, tl, tm);
build_st(rv, tm+1, tr);
st[v]=st[rv];
}
}
void update(int v, int tl, int tr, int ind) {
if(tl==tr) {
__[tl]^=1;
st[v]=(__[tl]?-1:flat[tl]);
} else {
if(ind<=tm)
update(lv, tl, tm, ind);
else
update(rv, tm+1, tr, ind);
st[v]=st[(st[rv]==-1?lv:rv)];
}
}
int query(int v, int tl, int tr, int l, int r) {
if(tl==l&&tr==r)
return st[v];
if(r<=tm)
return query(lv, tl, tm, l, r);
if(l>tm)
return query(rv, tm+1, tr, l, r);
int o=query(rv, tm+1, tr, tm+1, r);
if(o==-1)
return query(lv, tl, tm, l, tm);
return o;
}
int q(int s) {
int res=-1;
while(res==-1&&s!=-1) {
res=query(0, 0, N-1, pos[anc[s]], pos[s]);
s=par[anc[s]];
}
return res;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
ini(heavy, -1);
cin >> N >> M >> Q;
F0R(i, N-1) {
int U, V; cin >> U >> V;
--U; --V;
edge[i]=mp(U, V);
adj[U].pb(V);
adj[V].pb(U);
}
dfs_sz(-1, 0);
build_hld(-1, 0, 0);
build_st(0, 0, N-1);
F0R(i, M) {
int D, U, V; cin >> D;
--D;
tie(U, V)=edge[D];
if(par[U]==V)
swap(U, V);
if(!A[D])
info[q(U)]+=info[V]-Cinfo[V];
else
info[V]=Cinfo[V]=info[q(U)];
update(0, 0, N-1, pos[V]);
A[D]^=1;
}
F0R(i, Q) {
int C; cin >> C;
--C;
cout << info[q(C)] << '\n';
}
return 11^3^1<<3;
}
Compilation message (stderr)
synchronization.cpp:1:2: error: expected unqualified-id before 'if'
1 | if (heavy[u] == -1)
| ^~
synchronization.cpp:3:11: error: expected constructor, destructor, or type conversion before '(' token
3 | build_hld(u, heavy[u], r);
| ^
synchronization.cpp:4:2: error: expected unqualified-id before 'for'
4 | for (int v : adj[u]) {
| ^~~
synchronization.cpp:8:1: error: expected declaration before '}' token
8 | }
| ^
synchronization.cpp:26:8: error: 'maxn' was not declared in this scope
26 | int st[maxn];
| ^~~~
synchronization.cpp:27:9: error: 'maxn' was not declared in this scope
27 | bool __[maxn];
| ^~~~
synchronization.cpp: In function 'void build_st(int, int, int)':
synchronization.cpp:35:3: error: 'st' was not declared in this scope; did you mean 'std'?
35 | st[v]=flat[tl];
| ^~
| std
synchronization.cpp:35:9: error: 'flat' was not declared in this scope; did you mean 'float'?
35 | st[v]=flat[tl];
| ^~~~
| float
synchronization.cpp:39:3: error: 'st' was not declared in this scope; did you mean 'std'?
39 | st[v]=st[rv];
| ^~
| std
synchronization.cpp: In function 'void update(int, int, int, int)':
synchronization.cpp:45:3: error: '__' was not declared in this scope
45 | __[tl]^=1;
| ^~
synchronization.cpp:46:3: error: 'st' was not declared in this scope; did you mean 'std'?
46 | st[v]=(__[tl]?-1:flat[tl]);
| ^~
| std
synchronization.cpp:46:20: error: 'flat' was not declared in this scope; did you mean 'float'?
46 | st[v]=(__[tl]?-1:flat[tl]);
| ^~~~
| float
synchronization.cpp:52:3: error: 'st' was not declared in this scope; did you mean 'std'?
52 | st[v]=st[(st[rv]==-1?lv:rv)];
| ^~
| std
synchronization.cpp: In function 'int query(int, int, int, int, int)':
synchronization.cpp:58:10: error: 'st' was not declared in this scope; did you mean 'std'?
58 | return st[v];
| ^~
| std
synchronization.cpp: In function 'int q(int)':
synchronization.cpp:72:19: error: 'N' was not declared in this scope
72 | res=query(0, 0, N-1, pos[anc[s]], pos[s]);
| ^
synchronization.cpp:72:24: error: 'pos' was not declared in this scope
72 | res=query(0, 0, N-1, pos[anc[s]], pos[s]);
| ^~~
synchronization.cpp:72:28: error: 'anc' was not declared in this scope
72 | res=query(0, 0, N-1, pos[anc[s]], pos[s]);
| ^~~
synchronization.cpp:73:5: error: 'par' was not declared in this scope
73 | s=par[anc[s]];
| ^~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:79:2: error: 'cin' was not declared in this scope
79 | cin.tie(nullptr)->sync_with_stdio(false);
| ^~~
synchronization.cpp:80:6: error: 'heavy' was not declared in this scope
80 | ini(heavy, -1);
| ^~~~~
synchronization.cpp:80:2: error: 'ini' was not declared in this scope; did you mean 'int'?
80 | ini(heavy, -1);
| ^~~
| int
synchronization.cpp:81:9: error: 'N' was not declared in this scope
81 | cin >> N >> M >> Q;
| ^
synchronization.cpp:81:14: error: 'M' was not declared in this scope
81 | cin >> N >> M >> Q;
| ^
synchronization.cpp:81:19: error: 'Q' was not declared in this scope
81 | cin >> N >> M >> Q;
| ^
synchronization.cpp:82:6: error: 'i' was not declared in this scope
82 | F0R(i, N-1) {
| ^
synchronization.cpp:82:2: error: 'F0R' was not declared in this scope
82 | F0R(i, N-1) {
| ^~~
synchronization.cpp:89:2: error: 'dfs_sz' was not declared in this scope
89 | dfs_sz(-1, 0);
| ^~~~~~
synchronization.cpp:90:2: error: 'build_hld' was not declared in this scope; did you mean 'build_st'?
90 | build_hld(-1, 0, 0);
| ^~~~~~~~~
| build_st