제출 #519449

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519449		AriaH	Unique Cities (JOI19_ho_t5)	C++14	36 / 100	2066 ms	192216 KiB

joi2019_ho_t5

/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
typedef __int128 INT;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

template < typename T > using Tree = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, C[N], H[N], dp[N], mark[N], S[N], Ans[N];

set < pii > st;

vector < int > G[N];

void pre(int v, int P = 0)
{
	H[v] = H[P] + 1;
	dp[v] = 1;
	for(auto u : G[v])
	{
		if(u == P) continue;
		pre(u, v);
		dp[v] = max(dp[v], dp[u] + 1);
	}
}

bool cmp(int i, int j)
{
	return dp[i] < dp[j];
}

void dfs(int v, int P, int tp)
{
	/*printf("v = %d P = %d\n", v, P);
	for(auto x : st)
	{
		printf("%d %d\n", x.F, x.S);
	}
	printf("\n");
	*/
	vector < pii > hist;
	sort(all(G[v]), cmp);
	int Mx1 = 0, Mx2 = 0, id1 = -1;
	for(auto u : G[v])
	{
		if(u == P) continue;
		if(dp[u] > Mx1)
		{
			Mx2 = Mx1;
			Mx1 = dp[u];
			id1 = u;
		}
		else if(dp[u] > Mx2)
		{
			Mx2 = dp[u];
		}
	}
	while(SZ(st))
	{
		pii cu = *st.begin();
		cu.F = -cu.F;
		if(cu.F >= H[v] - Mx1)
		{
			hist.push_back(cu);
			st.erase(st.begin());
			mark[cu.S] = 0;
		}
		else
		{
			break;
		}
	}
	/*printf("Mx1 = %d Mx2 = %d after : \n", Mx1, Mx2);
	for(auto x : st)
	{
		printf("%d %d\n", x.F, x.S);
	}
	printf("\n");
	*/
	if(S[v] == tp) Ans[v] += SZ(st);
	if(!mark[C[v]])
	{
		mark[C[v]] = 1;
		st.insert({-H[v], C[v]});
	}
	for(auto u : G[v])
	{
		if(u == P || u == id1) continue;
		dfs(u, v, tp);
	}
	if(st.count({-H[v], C[v]}))
	{
		st.erase({-H[v], C[v]});
		mark[C[v]] = 0;
	}
	while(SZ(hist))
	{
		pii cu = hist.back();
		if(cu.F >= H[v] - Mx2)
		{
			break;
		}
		mark[cu.S] = 1;
		st.insert({-cu.F, cu.S});
		hist.pop_back();
	}
	if(!mark[C[v]])
	{
		mark[C[v]] = 1;
		st.insert({-H[v], C[v]});
	}
	if(id1 != -1)
	{
		dfs(id1, v, tp);
	}
	if(st.count({-H[v], C[v]}))
	{
		st.erase({-H[v], C[v]});
		mark[C[v]] = 0;
	}
	while(SZ(hist))
	{
		pii cu = hist.back();
		hist.pop_back();
		st.insert({-cu.F, cu.S});
		mark[cu.S] = 1;
	}
}

int fir[N], sec[N];

int main()
{
	fast_io;
	cin >> n >> m;
	for(int i = 1; i < n; 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];
	}
	pre(1, 0);
	int L = 0, R = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(H[i] > H[L]) L = i;
	}
	pre(L, 0);
	///printf("L = %d\n", L);
	for(int i = 1; i <= n; i ++)
	{
		fir[i] = H[i];
		if(H[i] > H[R]) R = i;
		///printf("i = %d H = %d dp = %d\n", i, H[i], dp[i]);
	}
	pre(R, 0);
	for(int i = 1; i <= n; i ++)
	{
		sec[i] = H[i];
		if(fir[i] > sec[i])
		{
			S[i] = 0;
		}
		else
		{
			S[i] = 1;
		}
	}
	pre(L, 0);
	///printf("R = %d\n", R);
	dfs(L, 0, 0);
	st.clear();
	memset(mark, 0, sizeof mark);
	pre(R, 0);
	for(int i = 1; i <= n; i ++)
	{
		///printf("i = %d H = %d dp = %d\n", i, H[i], dp[i]);
	}
	dfs(R, 0, 1);
	for(int i = 1; i <= n; i ++)
	{
		cout << Ans[i] << "\n";
	}

	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

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