#include <bits/stdc++.h>
using namespace std;
/// 123
const int MAXN = 1e5;
vector<int> adj[MAXN];
int f[MAXN];
int nxt[MAXN];
int par[MAXN];
pair<int, int> edge[MAXN];
#define time tme
int time = 1;
int last[MAXN];
int ans[MAXN];
int active[MAXN];
int tin[MAXN], out[MAXN];
int d[MAXN], rev[MAXN];
void prep(int u, int p) {
}
void dfs(int u, int p) {
par[u] = p;
f[u] = 1;
for (int i = 0; i < adj[u].size(); i++) {
if (adj[u][i] == p) {
swap(adj[u][i], adj[u].back());
adj[u].pop_back();
break;
}
}
for (int& v : adj[u]) {
d[v] = d[u] + 1;
dfs(v, u);
f[u] += f[v];
if (f[v] > f[adj[u][0]]) swap(v, adj[u][0]);
}
}
void hld(int u) {
rev[time] = u;
tin[u] = time++;
for (int v : adj[u]) {
nxt[v] = v == adj[u][0] ? nxt[u] : v;
hld(v);
}
out[u] = time;
}
template <class T>
class fenwick_t {
public:
vector<T> bit;
int n;
fenwick_t(int n = 0) : n(n) {
bit.resize(n + 1, 0);
}
void Update(int pos, T val) {
for (; pos <= n; pos += pos & -pos) {
bit[pos] += val;
}
}
T Get(int pos) {
T res = T(0);
for (; pos > 0; pos -= pos & -pos) {
res += bit[pos];
}
return res;
}
T Get(int l, int r) {
return Get(r) - (l ? Get(l - 1) : T(0));
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
edge[i] = {u, v};
}
prep(0, -1);
dfs(0, -1);
hld(0);
for (int i = 0; i < n - 1; i++) {
if (d[edge[i].first] < d[edge[i].second]) {
swap(edge[i].first, edge[i].second);
}
}
for (int i = 0; i < n; i++) ans[i] = 1;
fenwick_t<int> fw(n);
auto root = [&](int x) {
while (true) {
if (fw.Get(tin[nxt[x]], tin[x]) != tin[x] - tin[nxt[x]] + 1) {
int l = tin[nxt[x]], r = tin[x], res = -1;
while (l <= r) {
int mid = l + r >> 1;
if (fw.Get(mid, tin[x]) != tin[x] - mid + 1) {
res = rev[mid];
l = mid + 1;
} else {
r = mid - 1;
}
}
return assert(res != -1), res;
} else {
x = par[nxt[x]];
}
}
};
while (m--) {
int e;
cin >> e;
e--;
auto [x, y] = edge[e];
// y
// |
// x
int r = root(y);
active[e] ^= 1;
if (active[e]) {
ans[x] = ans[r] = ans[r] + ans[x] - last[e];
fw.Update(tin[x], +1);
} else {
ans[x] = last[e] = ans[r];
fw.Update(tin[x], -1);
}
}
while (q--) {
int u;
cin >> u;
u--;
cout << ans[root(u)] << '\n';
}
}
Compilation message
synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
synchronization.cpp: In lambda function:
synchronization.cpp:109:53: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
109 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5464 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5304 KB |
Output is correct |
| 4 |
Correct |
1 ms |
5468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 6 |
Correct |
2 ms |
5212 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5980 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5980 KB |
Output is correct |
| 9 |
Correct |
7 ms |
6096 KB |
Output is correct |
| 10 |
Correct |
80 ms |
13352 KB |
Output is correct |
| 11 |
Correct |
81 ms |
13288 KB |
Output is correct |
| 12 |
Correct |
118 ms |
21072 KB |
Output is correct |
| 13 |
Incorrect |
50 ms |
13256 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
15008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 6 |
Correct |
2 ms |
5212 KB |
Output is correct |
| 7 |
Correct |
14 ms |
6684 KB |
Output is correct |
| 8 |
Correct |
170 ms |
18836 KB |
Output is correct |
| 9 |
Correct |
169 ms |
19024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
19028 KB |
Output is correct |
| 2 |
Correct |
113 ms |
19252 KB |
Output is correct |
| 3 |
Correct |
118 ms |
19536 KB |
Output is correct |
| 4 |
Correct |
112 ms |
19284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5308 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6056 KB |
Output is correct |
| 7 |
Incorrect |
115 ms |
14056 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
