Submission #1276702

#TimeUsernameProblemLanguageResultExecution timeMemory
1276702coderg300711Synchronization (JOI13_synchronization)C++20
100 / 100
199 ms39176 KiB
#include <bits/stdc++.h>
using namespace std;

vector<int> a[100001], tr[800001];
int depth[100001], state[100001], cnt[100001], f[100001], mx[100001], p[100001], r[100001];
pair<int, int> edge[100001];
vector<pair<int, int>> change;

int find(int x){
	if(p[x]==x)return x;
	else return find(p[x]);
}

void unite(int u, int v){
	int ru = find(u), rv = find(v);
	if(ru!=rv){
		change.push_back({ru, rv});
		int tmp = mx[ru] + mx[rv] - f[v];
		mx[ru] = mx[rv] = tmp;
		if(r[ru] > r[rv]){
			p[rv] = ru;
			r[ru] += r[rv];
		}else{
			p[ru] = rv;
			r[rv] += r[ru];
		}
	}
}
void undo(){
	auto [u, v]=change.back();
	change.pop_back();
	int tmp = max(mx[u], mx[v]);
	mx[u] = mx[v] = tmp;
	if(r[u] > r[v]){
		r[u]-=r[v];
	}else r[v]-=r[u];
	p[u] = u;
	p[v] = v;
}

void dfs(int u, int p){
	for (int v:a[u]){
		if(v!=p){
			depth[v] = depth[u]+1;
			dfs(v, u);
		}
	}
}

void add(int node, int start, int end, int l, int r, int id){
	if(start > r || end < l){
		return;
	}
	if(l<=start && end<=r){
		tr[node].push_back(id);
		return;
	}
	int mid = (start+end)>>1;
	add(node<<1, start, mid, l, r, id);
	add((node<<1)+1, mid+1, end, l, r, id);
}

void query(int node, int start, int end){
	for (int id:tr[node]){
		auto [u, v] = edge[id];
		if(depth[u] > depth[v])swap(u, v);
		unite(u, v);
	}
	if(start!=end){
		int mid = (start+end)/2;
		query((node<<1), start, mid);
		query((node<<1)+1, mid+1, end);
	}
	for (int id:tr[node]){
		auto [u,v] = edge[id];
		if(depth[u] > depth[v])swap(u,v);
		f[v] = mx[find(v)];
		undo();
	}
}

signed main(){
	ios_base::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 u, v;
		cin >> u >> v;
		edge[i] = {u, v};
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for (int i =1;i<=n;++i){
		mx[i] = 1;
		r[i] = 1, p[i] = i;
	}
	dfs(1, 0);
	for (int i = 1;i<=m;++i){
		int id;
		cin >> id;
		if(state[id]==0){
			state[id] = i;
		}else{
			add(1, 1, m, state[id], i-1, id);
			state[id] = 0;
		}
	}
	for (int i = 1;i<n;++i){
		if(state[i]){
			add(1, 1, m, state[i], m, i);
			state[i] = 0;
		}
	}
	query(1, 1, m);
	while(q--){
		int u;
		cin >> u;
		cout << mx[find(u)] << '\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...