제출 #1314779

#제출 시각아이디문제언어결과실행 시간메모리
1314779WH8Synchronization (JOI13_synchronization)C++20
100 / 100
1025 ms36520 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
#define all(x) x.begin(), x.end()
#define iii tuple<int,int,int>
#define eb emplace_back

const int maxn=100005;
int fw[maxn];
void upd(int x, int v){
	while(x<=maxn){
		fw[x]+=v;
		x+=(x&(-x));
	}
}
int qry(int x){
	int ret=0;
	while(x>0){
		ret+=fw[x];
		x-=(x&-x);
	}
	return ret;
}

signed main(){
	int n,m,q;cin>>n>>m>>q;
	vector<pll> ed(n-1);
	int t=0;
	vector<int> in(n+1, 0), out(n+1, 0), a(n+1, 1), c(n+1, 0), dep(n+1, 0);
	vector<bool> on(n+1, 0);
	vector<vector<int>> up(n+1, vector<int>(20, 0)), al(n+1);
	for(int i=0;i<n-1;i++){
		cin>>ed[i].f>>ed[i].s;
		al[ed[i].f].pb(ed[i].s);
		al[ed[i].s].pb(ed[i].f);
	}
	auto dfs=[&](auto && dfs, int x, int p)->void{
		in[x]=t++;
		for(auto it: al[x]){
			if(it==p)continue;
			up[it][0]=x;
			dep[it]=dep[x]+1;
			dfs(dfs, it, x);
		}
		out[x]=t;
	};
	dfs(dfs, 1, 0);
	/*for(int i=1;i<=n;i++){
		printf("i %lld in %lld out %lld\n", i, in[i], out[i]);
	}*/
	for(int j=1;j<20;j++) for(int i=1;i<=n;i++) up[i][j]=up[up[i][j-1]][j-1];
	// ed[i].f is the child.
	for(int i=0;i<n-1;i++){
		if(in[ed[i].f] < in[ed[i].s])swap(ed[i].f, ed[i].s);
	}
	auto findpar=[&](int x)->int {
		// binary search for the parent of x;
		//printf("finding parent of x %lld\n", x);
		int par=x, lo=0, hi=dep[x], m, cp=qry(in[x]);
		//printf("cp is %lld\n", cp);
		while(hi >= lo){
			m=(hi+lo)/2;
			int anc=x;
			for(int j=0;j<20;j++) if((1<<j) & m) anc=up[anc][j];
			//printf("trying %lldth ancestor anc %lld\n", m, anc);
			int path=cp - qry(in[anc]);
			//printf("path is %lld\n", path);
			assert(path >= 0 and path <= m);
			if(path==m){
				lo=m+1;
				par=anc;
			}
			else {
				hi=m-1;
			}
		}
		if(par==0)par=1; // if everything path is on, parent is just the root.
		return par;
	};
	while(m--){
		//cout<<endl<<endl;
		int l;cin>>l;
		l--;
		int x=ed[l].f;
		if (!on[l]) { // turn on 
			//printf("TURNING ON x %lld\n", x);
			upd(in[x], 1);
			upd(out[x], -1);
		}
		int par=findpar(x);
		//printf("parent of %lld is %lld \n", x, par);
		if(on[l]){
			a[x]=a[par];
			c[x]=a[x];
			upd(in[x], -1);
			upd(out[x], 1);
		}
		else {
			assert(par != x); 
			a[par]=a[x] + a[par] - c[x];
		}
		on[l]=!on[l];
	}

	while(q--){
		int s;cin>>s;
		cout<<a[findpar(s)]<<"\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...