#include <bits/stdc++.h>
#define fi first
#define se second
#define sajz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5+7, P = 20, B = 1<<17;
int n, m, q, timer = -1, tin[N], tout[N], up[N][P];
int val[N], last[N], ind[N], tree[B*2];
pair<int,int> edge[N];
vector<int> g[N];
bool active[N];
void dfs(int v, int par){
up[v][0] = par;
for (int i=1; i<P; i++) up[v][i] = up[up[v][i-1]][i-1];
tin[v] = ++timer;
val[v] = 1;
for (auto u : g[v]){
if (u == par) continue;
dfs(u, v);
}
tout[v] = timer;
}
void update(int v, int a, int b, int p, int k, int x){
if (a > k || b < p) return;
else if (a >= p && b <= k){
tree[v] += x;
return;
}
int mid = (a+b) / 2;
update(v*2, a, mid, p, k, x); update(v*2+1, mid+1, b, p, k, x);
}
int query(int v){
v += B;
int res = 0;
while (v){
res += tree[v];
v /= 2;
}
return res;
}
int find_root(int v){
int u = v;
for (int i=P-1; i>=0; i--){
if (query(tin[up[u][i]]) == query(tin[v]) && query(tin[v]) > 0) u = up[u][i];
}
if (active[ind[u]]) return up[u][0];
return u;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> q;
for (int i=1; i<n; i++){
int a, b; cin >> a >> b;
edge[i] = {a, b};
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 1);
for (int i=1; i<n; i++){
auto [a, b] = edge[i];
if (tin[b] > tin[a]) swap(a, b);
ind[a] = i;
}
for (int i=0; i<m; i++){
int x; cin >> x;
auto [a, b] = edge[x];
if (tin[b] > tin[a]) swap(a, b);
//cout << "active: " << active[x] << " ----\n";
//cout << a << ' ' << b << ": " << find_root(a) << '\n';
//cout << val[a] << ' ' << val[b] << ": " << val[find_root(a)] << '\n';
if (!active[x]){
active[x] = true;
val[find_root(a)] += val[a] - last[a];
update(1, 0, B-1, tin[a], tout[a], 1);
}else{
val[a] = last[a] = val[find_root(a)];
update(1, 0, B-1, tin[a], tout[a], -1);
active[x] = false;
}
//cout << "val: " << val[find_root(a)] << '\n';
}
for (int i=0; i<q; i++){
int v; cin >> v;
//cout << v << ": " << find_root(v) << '\n';
cout << val[find_root(v)] << '\n';
}
return 0;
}
/*
5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5
*/
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:71:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
71 | auto [a, b] = edge[i];
| ^
synchronization.cpp:78:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
78 | auto [a, b] = edge[x];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
219 ms |
22184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
361 ms |
25336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
