#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct fenwick {
int n;
vector<int> tree;
fenwick(int _n) : n(_n+10), tree(n+10) {}
void update(int p, int v) {
for(p++; p<n; p+=p&-p) tree[p] += v;
}
int query(int p) {
int ans = 0;
for(p++; p; p-=p&-p) ans += tree[p];
return ans;
}
} fwt(2*N);
vector<int> g[N];
int n, m, q, in[N], out[N], timer = 1, up[N][20], A[N], B[N], vis[N], a[N], c[N];
void dfs(int u, int p) {
up[u][0] = p;
in[u] = timer++;
for(int i=1; i<20; i++)
up[u][i] = up[ up[u][i-1] ][i-1];
for(int v : g[u]) if(v ^ p) {
dfs(v, u);
}
out[u] = timer++;
}
int root(int u) {
for(int i=19; i>=0; i--) {
if(!up[u][i]) continue;
if(fwt.query(in[u]) == fwt.query(in[ up[u][i] ]))
u = up[u][i];
}
return u;
}
signed main() {
ios_base::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
cin >> n >> m >> q;
for(int i=1; i<n; i++) {
cin >> A[i] >> B[i];
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
dfs(1, 1);
for(int i=1; i<=n; i++) a[i] = 1;
for(int i=1; i<n; i++) {
if(in[A[i]] > in[B[i]]) swap(A[i], B[i]);
fwt.update(in[B[i]], 1);
fwt.update(out[B[i]], -1);
}
while(m--) {
int id; cin >> id;
int u = B[id];
int val = !vis[id] ? -1 : 1;
fwt.update(in[u], val);
fwt.update(out[u], -val);
if(!vis[id]) {
int v = root(A[id]);
a[v] += a[u] - c[u];
c[u] = a[u];
} else {
int v = root(A[id]);
a[u] = c[u] = a[v];
}
vis[id] ^= 1;
}
while(q--) {
int u; cin >> u;
cout << a[root(u)] << '\n';
}
}
# | 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... |