This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 2e5 + 5;
const int K = 18;
int n, m, q, numDFS;
int P[N][K], in[N], out[N], bit[N], last_val[N], res[N];
pii edge[N];
bool vs[N];
vector<int> g[N];
void update(int i, int val) {
for(; i <= n; i += i & -i) bit[i] += val;
}
void update(int l, int r, int val) {
update(l, val);
update(r + 1, -val);
}
int get(int i) {
int res = 0;
for(; i; i -= i & -i) res += bit[i];
return res;
}
int find(int u) {
for(int i = K - 1; i >= 0; --i) {
// check xem co cung tplt ko
if(get(in[u]) == get(in[P[u][i]])) {
u = P[u][i];
}
}
return u;
}
void dfs(int u, int p = 0) {
in[u] = ++numDFS;
P[u][0] = p;
for(int i = 1; i < K; ++i) P[u][i] = P[P[u][i - 1]][i - 1];
for(int v : g[u]) if(v != p) {
dfs(v, u);
}
out[u] = numDFS;
}
void solve() {
cin >> n >> m >> q;
for(int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
edge[i] = make_pair(u, v);
}
dfs(1);
for(int i = 1; i <= n; ++i) {
res[i] = 1;
update(in[i], out[i], 1);
}
for(int i = 1, pos; i <= m; ++i) {
cin >> pos;
auto [u, v] = edge[pos];
if(in[u] > in[v]) swap(u, v);
if(!vs[pos]) {
int rt = find(u);
// join (rt, v) : rt = root(u), v = root(v)
int nw = res[rt] + res[v] - last_val[pos];
res[rt] = nw;
update(in[v], out[v], -1);
} else {
res[v] = last_val[pos] = res[find(u)];
update(in[v], out[v], 1);
}
vs[pos] ^= 1;
}
while(q--) {
int u; cin >> u;
cout << res[find(u)] << '\n';
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int test = 1;
// cin >> test;
while(test--) solve();
return 0;
}
Compilation message (stderr)
synchronization.cpp: In function 'void solve()':
synchronization.cpp:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
64 | auto [u, v] = edge[pos];
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |