제출 #376791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376791		8e7	Mergers (JOI19_mergers)	C++14	48 / 100	3093 ms	36204 KiB

mergers

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
#define maxn 500005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
vector<int> adj[maxn], tree[maxn];
int col[maxn], cnt[maxn], siz[maxn], par[maxn], ind[maxn];
bool poss[maxn];

int cur;
void dfs(int n, int pa) {
	siz[n] = col[n] == cur ? 1 : 0;
	par[n] = pa;
	for (int v:adj[n]) {
		if (v != pa) {
			dfs(v, n);
			siz[n] += siz[v];
		}
	}
	if (siz[n] > 0 && siz[n] < cnt[cur]) poss[n] = true;
}

int find(int a) {
	return a == ind[a] ? a : ind[a] = find(ind[a]);
}
void Union(int a, int b) {
	ind[find(a)] = find(b);
}

int ans = 0;
void dfs2(int n, int par) {
	int chi = 0;
	for (int v:tree[n]) {
		if (v != par) {
			dfs2(v, n);
			chi++;
		}
	}
	if (chi == 0 || (n == 1 && chi == 1)) ans++;
}
int main() {
	io
	int n, k;
	cin >> n >> k;
	for (int i = 0;i < n - 1;i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1;i <= n;i++) {
		cin >> col[i];
		cnt[col[i]]++;
		ind[i] = i;
	}
	for (int i = 1;i <= k;i++) {
		for (int j = 1;j <= n;j++) siz[j] = 0;
		cur = i;
		dfs(1, 0);
	}
	for (int i = 1;i <= n;i++) {
		if (poss[i]) Union(i, par[i]);
	}
	int done = 1;
	for (int i = 1;i <= n;i++) {
		if (par[i] != 0 && !poss[i]) {
			done = 0;
			int a = find(i), b = find(par[i]);
			tree[a].push_back(b);
			tree[b].push_back(a);
		}
	}
	if (done) cout << 0 << "\n";
	else {
		dfs2(find(1), 0);
		cout << (ans + 1) / 2 << "\n";
	}
}
/*
5 4
1 2
2 3
3 4
3 5
1
2
1
3
4

5 4
1 2
2 3
3 4
4 5
1
2
3
4
1

2 2
1 2
1
2

 */

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