#include <bits/stdc++.h>
///#pragma GCC optimize("O3,unroll-loops")
///#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int LOG = 17;
int N, M, Q;
int timer, tin[100005], out[100005];
int res[100005], ST[400005], C[400005];
int P[100005][20], X[100005], Y[100005];
vector<int> adj[100005];
int state[100005];
void update(int v, int l, int r, int p, int val) {
if(l == r) {
ST[v] += val; return;
}
int md = (l + r) / 2;
if(p <= md) update(v * 2, l, md, p, val);
else update(v * 2 + 1, md + 1, r, p, val);
ST[v] = ST[v * 2] + ST[v * 2 + 1];
}
int query(int v, int l, int r, int lo, int hi) {
if(l > hi || r < lo) return 0;
if(l >= lo && r <= hi) return ST[v];
return query(v * 2, l, (l + r) / 2, lo, hi)
+ query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
}
void dfs(int v, int p) {
tin[v] = timer++; P[v][0] = p;
for(auto u : adj[v]) {
if(u == p) continue;
dfs(u, v);
}
out[v] = timer;
}
int findSet(int v) {
int K = query(1, 0, N, 0, tin[v]);
for(int l = LOG - 1; ~l; l--)
if(P[v][l] != -1 && query(1, 0, N, 0, tin[P[v][l]]) == K)
v = P[v][l];
return v;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> Q;
for(int l = 1; l <= N - 1; l++) {
cin >> X[l] >> Y[l];
adj[X[l]].push_back(Y[l]);
adj[Y[l]].push_back(X[l]);
}
dfs(1, 1);
for(int l = 1; l < LOG; l++)
for(int i = 1; i <= N; i++)
P[i][l] = P[P[i][l - 1]][l - 1];
for(int l = 1; l <= N; l++) {
update(1, 0, N, tin[l], -1);
update(1, 0, N, out[l], 1);
res[l] = 1;
}
for(int l = 1; l <= M; l++) {
int D; cin >> D;
int U = X[D], V = Y[D];
if(P[U][0] == V) swap(U, V);
U = findSet(U);
if(state[D]) {
res[V] = C[V] = res[U];
update(1, 0, N, tin[V], -1);
update(1, 0, N, out[V], 1);
}
else {
res[U] += res[V] - C[V];
update(1, 0, N, tin[V], 1);
update(1, 0, N, out[V], -1);
}
state[D] = !state[D];
}
for(int l = 1; l <= Q; l++) {
int K; cin >> K;
cout << res[findSet(K)] << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2728 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2772 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
5 ms |
2876 KB |
Output is correct |
7 |
Correct |
41 ms |
4408 KB |
Output is correct |
8 |
Correct |
43 ms |
4324 KB |
Output is correct |
9 |
Correct |
40 ms |
4308 KB |
Output is correct |
10 |
Correct |
510 ms |
19860 KB |
Output is correct |
11 |
Correct |
555 ms |
19804 KB |
Output is correct |
12 |
Correct |
674 ms |
24372 KB |
Output is correct |
13 |
Correct |
488 ms |
19704 KB |
Output is correct |
14 |
Correct |
346 ms |
18760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
367 ms |
21684 KB |
Output is correct |
2 |
Correct |
359 ms |
21456 KB |
Output is correct |
3 |
Correct |
268 ms |
23636 KB |
Output is correct |
4 |
Correct |
277 ms |
23372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2684 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2688 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
2 ms |
2644 KB |
Output is correct |
6 |
Correct |
6 ms |
2824 KB |
Output is correct |
7 |
Correct |
61 ms |
4912 KB |
Output is correct |
8 |
Correct |
852 ms |
25172 KB |
Output is correct |
9 |
Correct |
825 ms |
25284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
845 ms |
25284 KB |
Output is correct |
2 |
Correct |
465 ms |
24516 KB |
Output is correct |
3 |
Correct |
485 ms |
24604 KB |
Output is correct |
4 |
Correct |
464 ms |
24600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
5 ms |
2772 KB |
Output is correct |
6 |
Correct |
55 ms |
4448 KB |
Output is correct |
7 |
Correct |
690 ms |
20660 KB |
Output is correct |
8 |
Correct |
821 ms |
25292 KB |
Output is correct |
9 |
Correct |
551 ms |
20732 KB |
Output is correct |
10 |
Correct |
473 ms |
20116 KB |
Output is correct |
11 |
Correct |
507 ms |
22924 KB |
Output is correct |
12 |
Correct |
513 ms |
22844 KB |
Output is correct |
13 |
Correct |
479 ms |
24592 KB |
Output is correct |