Submission #417447

#TimeUsernameProblemLanguageResultExecution timeMemory
417447MohamedAhmed04Synchronization (JOI13_synchronization)C++17
100 / 100
318 ms25728 KiB
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

int n , m , q ;

int in[MAX] , out[MAX] , dep[MAX] , P[MAX][17] ;

int u[MAX] , v[MAX] , mark[MAX] ;
int val[MAX] , last[MAX] ;

vector< vector<int> >adj(MAX) ;

int tim = 0 ;

int bit[MAX] ;

void add(int i , int x)
{
	for(; i <= n ; i += (i & (-i)))
		bit[i] += x ;
}

int get(int i)
{
	int sum = 0 ;
	for(; i > 0 ; i -= (i & (-i)))
		sum += bit[i] ;
	return sum ;
}

void dfs(int node , int par)
{
	in[node] = ++tim ;
	P[node][0] = par ;
	for(int j = 1 ; j < 17 ; ++j)
		P[node][j] = P[P[node][j-1]][j-1] ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dfs(child , node) ;
	}
	out[node] = tim ;
}

int root(int node)
{
	for(int j = 16 ; j >= 0 ; --j)
	{
		if(!P[node][j])
			continue ;
		if(get(in[P[node][j]]) + (1 << j) == get(in[node]))
			node = P[node][j] ;
	}
	return node ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m>>q ;
	for(int i = 1 ; i <= n-1 ; ++i)
	{
		cin>>u[i]>>v[i] ;
		adj[u[i]].push_back(v[i]) ;
		adj[v[i]].push_back(u[i]) ;
	}
	dfs(1 , 0) ;
	for(int i = 1 ; i <= n ; ++i)
		val[i] = 1 ;
	while(m--)
	{
		int idx ;
		cin>>idx ;
		int x = u[idx] , y = v[idx] ;
		if(P[x][0] == y)
			swap(x , y) ;
		if(!mark[idx])
		{
			add(in[y] , 1) ;
			add(out[y]+1 , -1) ;
			mark[idx] = 1 ;
			val[root(y)] += val[y] - last[y] ;
		}
		else
		{
			mark[idx] = 0 ;
			last[y] = val[y] = val[root(y)] ;
			add(in[y] , -1) ;
			add(out[y]+1 , 1) ;
		}
	}
	while(q--)
	{
		int node ;
		cin>>node ;
		cout<<val[root(node)]<<"\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...