#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
vector <int> z[1000005];
int sta[1000005];
int fin[1000005];
int rev[1000005];
int tour;
int sz[1000005];
int same[1000005];
int active[1000005];
int par[100005][25];
int f[4000005];
int lazy[4000005];
int high[1000005];
pair<int,int> edge[1000005];
void push(int id){
if (lazy[id]!=0){
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
f[id*2]+=lazy[id];
f[id*2+1]+=lazy[id];
lazy[id]=0;
}
}
void dfs(int i,int parent){
tour++;
sta[i]=tour;
rev[tour]=i;
par[i][0]=parent;
for (auto p:z[i]){
if (p==parent){
continue;
}
high[p]=high[i]+1;
dfs(p,i);
}
fin[i]=tour;
}
void build(int id,int l,int r){
if (l==r){
f[id]=high[rev[l]];
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int x,int y,int val){
if (x>r || y<l){
return;
}
if (l>=x && y>=r){
f[id]+=val;
lazy[id]+=val;
return;
}
int mid=(l+r)/2;
push(id);
update(id*2,l,mid,x,y,val);
update(id*2+1,mid+1,r,x,y,val);
}
int get(int id,int l,int r,int pos){
if (l==r){
return f[id];
}
int mid=(l+r)/2;
push(id);
if (pos<=mid){
return get(id*2,l,mid,pos);
}else{
return get(id*2+1,mid+1,r,pos);
}
}
int ancestor(int x){
int val=get(1,1,tour,sta[x]);
for (int i=20;i>=0;i--){
int nxt=par[x][i];
if (nxt!=0 && get(1,1,tour,sta[nxt])==val){
x=par[x][i];
}
}
return x;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b >> c;
for (int i=1;i<a;i++){
int x,y;
cin >> x >> y;
z[x].push_back(y);
z[y].push_back(x);
edge[i]={x,y};
}
tour=0;
high[1]=0;
dfs(1,0);
par[0][0]=0;
for (int j=1;j<=20;j++){
for (int i=0;i<=a;i++){
par[i][j]=par[par[i][j-1]][j-1];
}
}
for (int i=1;i<=a;i++){
sz[i]=1;
same[i]=0;
active[i]=0;
}
build(1,1,tour);
int q=1;
while (b--){
int t;
cin >> t;
auto [x,y]=edge[t];
if (par[y][0]==x){
swap(x,y);
}
if (!active[t]){
int anc=ancestor(y);
// cout << t << " " << anc << " ";
sz[anc]+=sz[x]-same[x];
update(1,1,tour,sta[x],fin[x],-1);
// cout << sz[anc] << "\n";
}else{
int anc=ancestor(y);
sz[x]=sz[anc];
same[x]=sz[anc];
update(1,1,tour,sta[x],fin[x],1);
}
active[t]=1-active[t];
q++;
}
while (c--){
int x;
cin >> x;
int anc=ancestor(x);
cout << sz[anc] << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |