Submission #107427

#	Time	Username	Problem	Language	Result	Execution time	Memory
107427		faceless	Mergers (JOI19_mergers)	C++14	100 / 100	1722 ms	136952 KiB

mergers

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 10;
const int maxl = 21;
int cnt, par[maxn][maxl + 2], h[maxn], s[maxn], sz[maxn], psz[maxn], dp[maxn];
vector<int> t[maxn], vec[maxn];
bool pd[maxn];

void DFS(int v){
	sz[v] = 1;
	for (auto u : t[v]){
		if (u != par[v][0]){
			DFS(u);
			sz[v] += sz[u];
			psz[v] += psz[u];
			dp[v] += dp[u];
		}
	}
	if (dp[v] == 0 and sz[v] == psz[v] and par[v][0] != -1){
		cnt ++;
		dp[v] = 1;
		pd[v] = 1;
	}
}

int lca(int v, int u){
	if (h[v] < h[u])
		swap(v, u);
//	cout << "LCA " << v << " " << u << " -> ";
	for (int i = maxl - 1; i >= 0; i--)
		if (h[v] - (1 << i) >= h[u])
			v = par[v][i];
//	cout << v << endl;
	if (v == u)
		return v;
	for (int i = maxl - 1; i >= 0; i--){
		if (par[v][i] != par[u][i]){
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}

void dfs(int v, int p = -1){
	par[v][0] = p;
	for (int i = 1; i < maxl and par[v][i - 1] != -1; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for (auto u : t[v]){
		if (u != p){
			h[u] = h[v] + 1;
			dfs(u, v);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n - 1; i++){
		int v, u;
		cin >> v >> u;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	int nonleaf = -1;
	for (int v = 1; v <= n; v++)
		if (t[v].size() > 1)
			nonleaf = v;
	memset(par, -1, sizeof par);
	dfs(nonleaf);

	for (int v = 1; v <= n; v++){
		cin >> s[v];
		vec[s[v]].push_back(v);
	}
	for (int i = 1; i <= k; i++){
		int v = vec[i][0];
		for (auto u : vec[i])
			v = lca(v, u);
		psz[v] += vec[i].size();
	}
	DFS(nonleaf);
	bool flag = 0;
	for (int v = 1; v <= n; v++)
		if (par[v][0] != -1 and pd[v] == 0 and dp[v] == cnt and psz[v] == sz[v])
			flag = 1;
	if (cnt & 1)
		cout << (cnt + 1) / 2 << endl;
	else
		cout << cnt / 2 + flag << endl;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30