Submission #1314254

#TimeUsernameProblemLanguageResultExecution timeMemory
1314254boclobanchatSynchronization (JOI13_synchronization)C++20
100 / 100
170 ms21532 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...