Submission #1015582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015582		THXuan	Capital City (JOI20_capital_city)	C++14	11 / 100	3048 ms	25428 KiB

capital_city

// subtask 1 && subtask 2
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e9
using namespace std;
typedef long long ll;

int v[200005], p[200005];
vector<int>adj[200005], c[200005];

void dfs(int s, int e) {
	for (auto u : adj[s]) {
		if (u == e) continue;
		p[u] = s;
		dfs(u, s);
	}
}

void solve()
{
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n - 1; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		c[v[i]].push_back(i);
	}
	int ans = INF;
	for (int i = 1; i <= k; i++) {
		dfs(c[i][0], 0);
		queue<int>q;
		for (auto u : c[i]) {q.push(u); }
		vector<bool>visited(k + 1, false);
		visited[i] = true;
		int anss = 0;
		while (q.size()) {
			int u = q.front(); q.pop();
			if (p[u] != 0 && v[p[u]] != v[u] && !visited[v[p[u]]]) {
				visited[v[p[u]]] = true;
				++anss;
				for (auto x : c[v[p[u]]])q.push(x);
			}
		}
		ans = min(ans, anss);
	}
	cout << ans << "\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;//cin>>t;
	while (t--) solve();
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59