Submission #1033016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033016		juicy	Mergers (JOI19_mergers)	C++17	100 / 100	1081 ms	103388 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5e5 + 5, LG = 19;

int n, k;
int dep[N], pr[LG][N], lab[N], top[N], lst[N], deg[N];
vector<int> g[N];

void dfs(int u) {
	for (int v : g[u]) {
		if (v != pr[0][u]) {
			pr[0][v] = u;
			for (int j = 1; j < LG; ++j) {
				pr[j][v] = pr[j - 1][pr[j - 1][v]];
			}
			dep[v] = dep[u] + 1;
			dfs(v);
		}
	}
} 

int get(int u) {
	return lab[u] < 0 ? u : lab[u] = get(lab[u]);
}

void unite(int u, int v) {
	u = get(u);
	v = get(v);
	if (u != v) {
		if (lab[u] > lab[v]) {
			swap(u, v);
		}
		lab[u] += lab[v];
		lab[v] = u;
		if (dep[top[v]] < dep[top[u]]) {
			top[u] = top[v];
		}
	}
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	for (int j = LG - 1; ~j; --j) {
		if (dep[u] - (1 << j) >= dep[v]) {
			u = pr[j][u];
		}
	}
	if (u == v) {
		return u;
	}
	for (int j = LG - 1; ~j; --j) {
		if (pr[j][u] ^ pr[j][v]) {
			u = pr[j][u], v = pr[j][v];
		}
	}
	return pr[0][u];
}

void up(int u, int x) {
	while (dep[top[get(u)]] >= dep[x]) {
		unite(u, top[get(u)]);
	}
}

void add(int u, int v) {
	int x = lca(u, v);
	up(u, x);
	up(v, x);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> k;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dep[1] = 1;
	dfs(1);
	for (int i = 1; i <= n; ++i) {
		top[i] = pr[0][i];
		lab[i] = -1;
	}
	for (int i = 1; i <= n; ++i) {
		int c; cin >> c;
		if (lst[c]) {
			add(lst[c], i);
		}
		lst[c] = i;
	}
	for (int u = 1; u <= n; ++u) {
		for (int v : g[u]) {
			if (get(u) != get(v)) {
				++deg[get(v)];
			}
		}
	}
	int cnt = count(deg + 1, deg + n + 1, 1);
	if (cnt & 1) {
		cout << cnt / 2 + 1;
		exit(0);
	}
	cout << cnt / 2;
	return 0;
}

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