Submission #306680

#	Time	Username	Problem	Language	Result	Execution time	Memory
306680		pit4h	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	582 ms	37996 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+1;
int n, m, c[N], d[N], h[N], diam, v1, v2, root, M[N], distinct;
bool calced[N];
vector<int> g[N], path;
void predfs(int x, int p) {
	d[x] = d[p] + 1;
	h[x] = 0;
	for(int i: g[x]) {
		if(i!=p) {
			predfs(i, x);
			h[x] = max(h[x], h[i] + 1);
		}
	}
}
bool added[N];
void _add(int x) {
	if(added[x]) return;
	M[c[x]]++;
	added[x]=1;
	if(M[c[x]]==1) distinct++;
}
void _del(int x) {
	if(!added[x]) return;
	M[c[x]]--;
	added[x]=0;
	if(M[c[x]]==0) distinct--;
}
int cnt[N];
int ans[N];
void solve(int x, int p) { 
	int len = path.size();
	int max_child = 0;
	for(int i: g[x]) {
		if(i != p && (!max_child || h[max_child] < h[i])) {
			max_child = i;
		}
	}
	for(int i: g[x]) {
		if(i != p && (x == root || i != max_child)) {
			for(int j=max(0, len-h[i]-1); j<len; ++j) {
				cnt[j]++;
				if(cnt[j]==1) {
					_del(path[j]);
				}
			}
		}
	}
	if(x != root) {
		int del1=(len-1)-h[x]-1, del2=del1+1;
		if(del1>=0) {
			cnt[del1]--;
			if(cnt[del1]==0) _add(path[del1]);
		}
		if(del2>=0) {
			cnt[del2]--;
			if(cnt[del2]==0) _add(path[del2]);
		}
		cnt[len-1]++;
		if(cnt[len-1]==1) _del(path[len-1]);
	}
	ans[x] = max(ans[x], distinct);
	path.push_back(x);
	_add(x);
	for(int i: g[x]) {
		if(i != p) {
			solve(i, x);
		}
	}
	for(int i: g[x]) {
		if(i != p && (x == root || i != max_child)) {
			for(int j=max(0, len-h[i]-1); j<len; ++j) {
				cnt[j]--;
				if(cnt[j]==0) {
					_add(path[j]);
				}
			}
		}
	}
	if(x != root) {
		int del1=(len-1)-h[x]-1, del2=del1+1;
		if(del1>=0) {
			cnt[del1]++;
			if(cnt[del1]==1) _del(path[del1]);
		}
		if(del2>=0) {
			cnt[del2]++;
			if(cnt[del2]==1) _del(path[del2]);
		}
		cnt[len-1]--;
		if(cnt[len-1]==0) _add(path[len-1]);
	}
	path.pop_back();
	_del(x);
}            
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=0; i<n-1; ++i) {
		int a, b; cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1; i<=n; ++i) {
		cin>>c[i];
	}
	predfs(1, 1);
	for(int i=1; i<=n; ++i) {
		if(d[i] > d[v1]) {
			v1 = i;
		}
	}
	diam = d[v1];
	d[v1] = 0;
	predfs(v1, v1);
	for(int i=1; i<=n; ++i) {
		if(d[i] > d[v2]) {
			v2 = i;
		}
	}

	root = v1;
	d[root] = 0;
	predfs(root, root);
	solve(v1, v1);	

	root = v2;
	d[root] = 0;
	predfs(root, root);
	solve(v2, v2);
	for(int i=1; i<=n; ++i) {
		cout<<ans[i]<<'\n';
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32