#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int ans[MAXN],pre[MAXN],sp[MAXN][20],fen[MAXN],L[MAXN],R[MAXN],tdfs=0;
pair<int,int> edge[MAXN];
vector<int> ds[MAXN];
bool ck[MAXN];
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
void dfs(int i,int pre)
{
sp[i][0]=pre,L[i]=++tdfs;
for(int j=1;j<=17;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
for(auto v:ds[i]) if(v!=pre) dfs(v,i);
R[i]=tdfs;
}
int findroot(int pos)
{
int ans=pos;
for(int i=17;i+1;i--) if(get(L[ans])-get(L[sp[ans][i]])==(1<<i)) ans=sp[ans][i];
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<n;i++)
{
int l,r;
cin>>l>>r;
ds[l].push_back(r),ds[r].push_back(l),edge[i]={l,r};
}
dfs(1,1);
for(int i=1;i<=n;i++) ans[i]=1;
for(int i=1;i<=m;i++)
{
int pos;
cin>>pos;
ck[pos]=1-ck[pos];
int l=edge[pos].first,r=edge[pos].second;
if(sp[l][0]!=r) swap(l,r);
if(ck[pos])
{
update(L[l],n,1);
update(R[l]+1,n,-1);
ans[findroot(l)]+=ans[l]-pre[l];
}
else
{
pre[l]=ans[l]=ans[findroot(l)];
update(L[l],n,-1);
update(R[l]+1,n,1);
}
}
while(q--)
{
int res;
cin>>res;
cout<<ans[findroot(res)]<<"\n";
}
}
| # | 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... |