Submission #211311

#	Time	Username	Problem	Language	Result	Execution time	Memory
211311		Kevin_Zhang_TW	Unique Cities (JOI19_ho_t5)	C++17	100 / 100	418 ms	40812 KiB

joi2019_ho_t5

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
const int maxn = 300010;
int n, m;
int c[maxn];
vector<int> edge[maxn];
int len[maxn], fp[maxn], dep[maxn], son[maxn];
namespace st{
	int st[maxn], stl;
	int cnt[maxn], _res;
	void _add_in(int a, int d) {
		if (cnt[a] == 0) ++_res;
		if ((cnt[a]+=d) == 0) --_res;
	}
	void push(int id) {
		_add_in(c[id], 1);
		st[stl++] = id;
	}
	void pop() {
		assert(--stl >= 0);
		_add_in(c[st[stl]], -1);
	}
	int back() {
		return st[stl-1];
	}
	void pop_dep(int d) {
		while (stl && dep[back()] >= d) pop();
	}
	int query() {
		return _res;
	}
}
int getfar(int now, int last = -1) {
	len[now] = 0;
	fp[now] = now;
	for (int u : edge[now]) if (u != last) {
		int v = getfar(u, now);
		if (len[u]+1 > len[now])
			fp[now] = v, len[now] = len[u]+1;
	}
	return fp[now];
}
int res[maxn];
void getinfo(int now, int last = -1) {
	static int d;
	len[now] = 0;
	dep[now] = ++d;
	son[now] = -1;
	for (int u : edge[now]) if (u != last) {
		getinfo(u, now);
		if (len[u]+1 > len[now]) {
			son[now] = u;
			len[now] = len[u]+1;
		}
	}
	--d;
}
void getres(int now, int last = -1) {
	if (son[now] == -1) {
		res[now] = max(res[now], st::query());
		//cerr << "now " << now << " : " << st::query() << " son : " << son[now] << '\n';
		return;
	}
	int mx = 0;
	for (int u : edge[now]) if (u != last && u != son[now])
		mx = max(mx, len[u]+1);
	st::pop_dep(dep[now] - mx);
	st::push(now);
	getres(son[now], now);
	for (int u : edge[now]) if (u != last && u != son[now]) {
		st::pop_dep(dep[now] - len[now]);
		st::push(now);
		getres(u, now);
	}
	st::pop_dep(dep[now] - len[now]);
	//cerr << "now " << now << " : " << st::query() << " son : " << son[now] << '\n';
	res[now] = max(res[now], st::query());
}
void get_res(int root) {
	getinfo(root);
	getres(root);
	//cerr << '\n';
}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int a, b, i = 1;i < n;++i) {
		cin >> a >> b;
		edge[a].pb(b);
		edge[b].pb(a);
	}
	for (int i = 1;i <= n;++i)
		cin >> c[i];
	int a = getfar(1), b = getfar(a);
	//cerr << "dia " << a << ' ' << b << '\n';
	get_res(a), get_res(b);
	for (int i = 1;i <= n;++i)
		cout << res[i] << '\n';
}

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