#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
const int LN = 1e5 + 7;
int N,M,Q,a[LN],p[LN],lift[LN][20];
vector < int > TREE[LN] , trav = {0};
pair < int , int > ind[LN];
struct SEGT{
vector < int > tree;
int tsz;
void init(int x){
tsz = x;
tree.assign(4*x,0);
}
void _update(int ind , int l , int r , int ul , int ur , int uv){
if(l >= ul and r <= ur)tree[ind] += uv;
else if(l > ur or r < ul)return;
else {
int mid = (l+r)/2;
_update(ind*2,l,mid,ul,ur,uv);
_update(ind*2+1,mid+1,r,ul,ur,uv);
}
}
void update(int ul , int ur , int uv){
_update(1,1,tsz,ul,ur,uv);
}
int _query(int ind , int l , int r , int qp){
if(l == r){
return tree[ind];
}
int mid = (l+r)/2;
if(mid >= qp)return _query(ind*2,l,mid,qp);
else return _query(ind*2+1,mid+1,r,qp);
}
int query(int qp){
return _query(1,1,tsz,qp);
}
} segt;
void dfs1(int node , int past){
ind[node].first = sz(trav);
trav.push_back(node);
lift[node][0] = past;
for(auto itr : TREE[node]){
if(itr == past)continue;
dfs1(itr,node);
}
ind[node].second = sz(trav);
}
inline void subtree_update(int node , int uv){
segt.update(ind[node].first , ind[node].second , uv);
}
int find_root(int node){
if(segt.query(ind[node].first) != segt.query(ind[lift[node][0]].first))return node;
for(int i = 19;i>=0;i--){
int newnode = lift[node][i];
if(segt.query(ind[node].first) == segt.query(ind[newnode].first))node = newnode;
}
return lift[node][0];
}
inline void merge(int u , int v){// u E par[v]
u = find_root(u);
v = find_root(v);
if(ind[u].first > ind[v].first)swap(u,v);
a[u] = a[u] + a[v] - p[v];
a[v] = p[v] = 0;
segt.update(ind[v].first,ind[v].second,-1);
}
inline void unmerge(int u, int v){// u E par[v]
if(ind[u].first > ind[v].first)swap(u,v);
u = find_root(u);
a[v] = p[v] = a[u];
segt.update(ind[v].first,ind[v].second,1);
}
void dfs2(int node , int past){
if(a[node] == 0)a[node] = a[past];
for(auto itr : TREE[node]){
if(itr == past)continue;
dfs2(itr,node);
}
}
void solve(){
cin >> N >> M >> Q;
for(int i = 1;i<=N;i++)a[i] = 1;
vector < array < int , 3 > > edges;
for(int i = 1;i<N;i++){
int XI,YI;cin >> XI >> YI;
TREE[XI].push_back(YI);
TREE[YI].push_back(XI);
edges.push_back({XI,YI,0});
}
dfs1(1,1);
segt.init(sz(trav));
for(int i = 1;i<sz(trav);i++){
segt.update(i,i,trav[i]);
}
lift[1][0] = 1;
for(int i = 1;i<20;i++){
for(int j = 1;j<=N;j++){
lift[j][i] = lift[lift[j][i-1]][i-1];
}
}
while(M--){
int DJ;cin >> DJ;DJ--;
if(edges[DJ][2])unmerge(edges[DJ][0] , edges[DJ][1]);
else merge(edges[DJ][0] , edges[DJ][1]);
edges[DJ][2] = 1 - edges[DJ][2];
}
dfs2(1,1);
while(Q--){
int CK;cin >> CK;
cout << a[CK] << endl;
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}
/*
- dont loop over same ideas
- abandon the problem if you have no idea
- think about implementation
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
210 ms |
24288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
380 ms |
28336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
