제출 #208300

#제출 시각아이디문제언어결과실행 시간메모리
208300YJU동기화 (JOI13_synchronization)C++14
100 / 100
401 ms40752 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=4e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll n,x,y,m,q,bit[N],in[N],out[N],ti=1,lca[N][21],cd,ans[N],last[N],B[N];
vector<pll> edge;
vector<ll> v[N];

void DFS(ll nd,ll pa){
	lca[nd][0]=pa;
	in[nd]=ti++;
	ans[nd]=1;
	for(ll i=1;i<=20&&lca[nd][i-1];i++)lca[nd][i]=lca[lca[nd][i-1]][i-1];
	for(auto i:v[nd]){
		if(i==pa)continue;
		DFS(i,nd);
	}
	out[nd]=ti;
}

void mod(ll id,ll dx){
	while(id<N)bit[id]+=dx,id+=(id&-id);
}

ll query(ll id){
	ll tmp=0;while(id)tmp+=bit[id],id-=(id&-id);return tmp;
}

ll find(ll id){
	ll tmp=id;
	for(ll i=20;i>=0;i--)if(lca[tmp][i]&&query(in[lca[tmp][i]])==query(in[id]))tmp=lca[tmp][i];
	return tmp;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>q;
	REP(i,n-1){
		cin>>x>>y;
		edge.pb(mp(x,y));
		v[x].pb(y);v[y].pb(x);
	}
	DFS(1,0);
	REP1(i,n)mod(in[i],-1),mod(out[i],1);
	REP(i,m){
		cin>>cd;
		y=edge[cd-1].Y;x=edge[cd-1].X;
		if(lca[y][0]==x)swap(x,y);
		if(B[cd-1]){
			ans[x]=last[x]=ans[find(y)];
			mod(in[x],-1),mod(out[x],1);
		}else{
			ans[find(y)]+=ans[x]-last[x];
			mod(in[x],1),mod(out[x],-1);
		}
		B[cd-1]=1-B[cd-1];
	}
	while(q--)cin>>x,cout<<ans[find(x)]<<"\n";
	return 0;
}


#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...