Submission #518999

#	Time	Username	Problem	Language	Result	Execution time	Memory
518999		Keshi	Unique Cities (JOI19_ho_t5)	C++17	100 / 100	1056 ms	73652 KiB

joi2019_ho_t5

//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
const int inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)

ll pw(ll a, ll b){
	ll c = 1;
	while(b){
		if(b & 1) c = c * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return c;
}

int n, m, c[maxn], d[maxn], mx, r1, r2, dd[maxn], ans[maxn], prv[maxn];
vector<int> g[maxn];
bool vis[maxn];
int seg[maxn << 2], lz[maxn << 2], cnt[maxn << 2];

void bld(int id, int s, int e){
	seg[id] = lz[id] = 0;
	cnt[id] = e - s;
	if(e - s == 1) return;
	int mid = (s + e) >> 1;
	bld(lc, s, mid);
	bld(rc, mid, e);
	return;
}

void upd(int id, int s, int e, int l, int r, int x){
	if(r <= s || e <= l) return;
	if(l <= s && e <= r){
		seg[id] += x;
		lz[id] += x;
		return;
	}
	int mid = (s + e) >> 1;
	seg[lc] += lz[id];
	lz[lc] += lz[id];
	seg[rc] += lz[id];
	lz[rc] += lz[id];
	lz[id] = 0;
	upd(lc, s, mid, l, r, x);
	upd(rc, mid, e, l, r, x);
	seg[id] = min(seg[lc], seg[rc]);
	cnt[id] = 0;
	if(seg[id] == seg[lc]) cnt[id] += cnt[lc];
	if(seg[id] == seg[rc]) cnt[id] += cnt[rc];
	return;
}
int get(int id, int s, int e, int l, int r){
	if(r <= s || e <= l) return inf;
	if(l <= s && e <= r) return seg[id];
	int mid = (s + e) >> 1;
	seg[lc] += lz[id];
	lz[lc] += lz[id];
	seg[rc] += lz[id];
	lz[rc] += lz[id];
	lz[id] = 0;
	return min(get(lc, s, mid, l, r), get(rc, mid, e, l, r));
}

void difs(int v){
	vis[v] = 1;
	if(d[v] > d[mx]) mx = v;
	for(int u : g[v]){
		if(vis[u]) continue;
		d[u] = d[v] + 1;
		difs(u);
	}
	return;
}
vector<int> gg[maxn];

void prep(int v, int p = -1){
	gg[v].clear();
	dd[v] = d[v];
	for(int u : g[v]){
		if(u == p) continue;
		d[u] = d[v] + 1;
		gg[v].pb(u);
		prep(u, v);
		dd[v] = max(dd[v], dd[u]);
	}
	return;
}

void solve(int v){
	upd(1, 0, n, d[v] - (dd[v] - d[v]), d[v], 1);
	ans[v] = max(ans[v], cnt[1] - (n - d[v]));
	upd(1, 0, n, d[v] - (dd[v] - d[v]), d[v], -1);
	vector<pll> vec;
	vec.pb(Mp(-d[v], v));
	for(int u : gg[v]){
		vec.pb(Mp(-dd[u], u));
	}
	sort(all(vec));
	for(int u : gg[v]){
		int x = d[v] - (-vec[0].F - d[v]);
		if(u == vec[0].S){
			x = d[v] - (-vec[1].F - d[v]);
		}
		upd(1, 0, n, x, d[v], 1);
		int pr = prv[c[v]];
		if(pr == 0 || get(1, 0, n, d[pr], d[pr] + 1) != 0){
			prv[c[v]] = v;
		}
		else{
			upd(1, 0, n, d[v], d[v] + 1, 1);
		}
		solve(u);
		if(prv[c[v]] == v){
			prv[c[v]] = pr;
		}
		else{
			upd(1, 0, n, d[v], d[v] + 1, -1);
		}
		upd(1, 0, n, x, d[v], -1);
	}
	return;
}

int main(){
	fast_io;

	cin >> n >> m;
	for(int i = 1; i < n; i++){
		int v, u;
		cin >> v >> u;
		g[v].pb(u);
		g[u].pb(v);
	}
	for(int i = 1; i <= n; i++){
		cin >> c[i];
	}
	d[1] = 0;
	difs(1);
	r1 = mx;
	fill(vis, vis + n + 10, 0);
	d[r1] = 0;
	difs(r1);
	r2 = mx;
	d[r1] = 0;
	prep(r1);
	bld(1, 0, n);
	solve(r1);
	d[r2] = 0;
	prep(r2);
	bld(1, 0, n);
	solve(r2);

	for(int i = 1; i <= n; i++){
		cout << ans[i] << "\n";
	}
	
	return 0;
}

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