제출 #519484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519484		AriaH	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	159 ms	30308 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 = 2e5 + 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, check[N], C[N], H[N], dp[N], mark[N], S[N], Ans[N], node[N];

set < int > 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];
}

inline void Add(int v)
{
	if(!mark[C[v]])
	{
		check[v] ++;
		assert(check[v] - SZ(G[v]) <= 40);
		mark[C[v]] = 1;
		st.insert({-H[v]});
	}
}

inline void Del(int v)
{
	if(st.count(-H[v]))
	{
		st.erase(-H[v]);
		mark[C[v]] = 0;
	}
}

void dfs(int v, int P, int tp)
{
	node[H[v]] = v;
	vector < int > 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))
	{
		int cu = *st.begin();
		cu = -cu;
		int U = node[cu];
		if(cu >= H[v] - Mx1)
		{
			hist.push_back(cu);
			Del(U);
		}
		else
		{
			break;
		}
	}
	if(S[v] == tp) Ans[v] += SZ(st);
	Add(v);
	for(auto u : G[v])
	{
		if(u == P || u == id1) continue;
		dfs(u, v, tp);
	}
	Del(v);
	while(SZ(hist))
	{
		int cu = hist.back();
		int U = node[cu];
		if(cu >= H[v] - Mx2)
		{
			break;
		}
		Add(U);
		hist.pop_back();
	}
	Add(v);
	if(id1 != -1)
	{
		dfs(id1, v, tp);
	}
	Del(v);
	while(SZ(hist))
	{
		int cu = hist.back();
		int U = node[cu];
		hist.pop_back();
		Add(U);
	}
}

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);
	int L = 0, R = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(H[i] > H[L]) L = i;
	}
	pre(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);
	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);
	dfs(L, 0, 0);
	st.clear();
	memset(mark, 0, sizeof mark);
	memset(check, 0, sizeof check);
	pre(R);
	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: 0 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32