#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e5+ 5, N = 1e6;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, m, q;
vector<int> adj[nmax];
int h[nmax], par[nmax], sz[nmax];
void dfs(int u, int p){
sz[u] = 1;
for(auto v : adj[u]){
if(v == p) continue;
h[v] = h[u] + 1;
par[v] = u;
dfs(v, u);
sz[u] += sz[v];
}
}
int head[nmax], ind[nmax], pos[nmax], Time = 0, nchain = 1;
int lol[nmax];
void dfs_2(int u, int p){
if(!head[nchain]) head[nchain] = u;
ind[u] = nchain;
pos[u] = ++Time;
lol[Time] = u;
int idx = -1;
for(auto v : adj[u]){
if(v == p) continue;
if(idx == -1 || sz[v] > sz[idx]) idx = v;
}
if(idx != -1) dfs_2(idx, u);
for(auto v : adj[u]){
if(v == p) continue;
if(idx == v) continue;
++nchain;
dfs_2(v, u);
}
}
int rev[nmax];
struct SEG_1{
int tree[nmax << 2];
void update(int id, int l,int r, int u, int val){
if(l > u || r < u) return;
if(l == r){
tree[id] = val;
return;
}
int mid = r + l >> 1;
update(id << 1, l, mid, u, val);
update(id << 1 | 1, mid + 1, r, u, val);
tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
int get(int id, int l,int r, int u, int v){
if(tree[id] == 1) return -1;
if(l >= u && r <= v){
while(l != r){
int mid = r + l >> 1;
if(!tree[id << 1 | 1]){
id = id << 1 | 1;
l = mid + 1;
}
else {
id = id << 1;
r = mid;
}
}
return l;
}
int mid = r + l >> 1;
if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v);
if(mid + 1 > v) return get(id << 1, l, mid, u, v);
int t1 = get(id << 1 | 1, mid + 1, r, u, v);
if(t1 != -1) return t1;
return get(id << 1, l, mid, u, v);
}
}one;
pii a[nmax];
int res[nmax],last[nmax];
int Find(int u){
int uchain = ind[u], achain = ind[1];
while(1){
if(uchain == achain){
int kq = one.get(1, 1, n, pos[1], pos[u]);
return lol[kq];
}
int kq = one.get(1, 1, n, pos[head[uchain]], pos[u]);
if(kq != -1) return lol[kq];
u = par[head[uchain]];
uchain = ind[u];
}
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m >> q;
for(int i = 1; i < n; ++i){
cin >> a[i].fi >> a[i].se;
adj[a[i].fi].push_back(a[i].se);
adj[a[i].se].push_back(a[i].fi);
}
dfs(1, -1);
dfs_2(1, -1);
for(int i = 1; i <= n; ++i){
int u = a[i].fi;
int v = a[i].se;
if(h[u] > h[v]) swap(u, v);
res[i] = 1;
}
for(int i = 1,x; i <= m; ++i){
cin >> x;
int u = a[x].fi, v= a[x].se;
if(!rev[x]){
one.update(1, 1, n, pos[v], 1);
int root = Find(v);
res[root] += res[v] - last[v];
}
else{
int root = Find(v);
one.update(1, 1, n, pos[v], 0);
res[v] = res[root];
last[v] = last[root];
}
rev[x] ^= 1;
}
for(int i = 1, x; i <= q; ++i){
cin >> x;
cout << res[Find(x)] << endl;
}
}
/*
*/
Compilation message
synchronization.cpp: In member function 'void SEG_1::update(int, int, int, int, int)':
synchronization.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid = r + l >> 1;
| ~~^~~
synchronization.cpp: In member function 'int SEG_1::get(int, int, int, int, int)':
synchronization.cpp:68:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid = r + l >> 1;
| ~~^~~
synchronization.cpp:80:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | int mid = r + l >> 1;
| ~~^~~
synchronization.cpp: At global scope:
synchronization.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
103 | main(){
| ^~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:124:13: warning: unused variable 'u' [-Wunused-variable]
124 | int u = a[x].fi, v= a[x].se;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
15444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
19724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
