[Codeforces #379 E. Anton and Tree]缩点+树上最长路

1. 题目链接

[Codeforces #379 E. Anton and Tree]

2. 题意描述

给定一个 N 个节点的树。树上每个节点i都有初始颜色 colori (0或者1) ， 相同颜色的且相邻的节点在同一个块中。每次操作可以将一个块中的所有节点颜色反转。问，将该树上所有节点颜色都变成0或者都变成1所需要的最少操作次数。

3. 解题思路

首先对原树用并查集缩点，并形成新的树。然后两次dfs求出树上最长链。以最长链的中点向两边扩散可能是最少的操作次数。那么答案就是树上最长链/2【向上取整】。

4. 实现代码

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int MX = 200000 + 5; int n, color[MX];; set<int> edge[MX]; int belong[MX]; int F(int x) { return -1 == belong[x] ? x : belong[x] = F(belong[x]); } inline void U(int u, int v) { u = F(u), v = F(v); if(u != v) belong[v] = u; } /** * 两次DFS求树上最长路 */ void dfs(int u, int pre, int dep, int& d, int& id) { int v; if(dep > d) { d = dep; id = u; } for(set<int>::iterator it = edge[u].begin(); it != edge[u].end(); it++) { v = *it; if(v == pre) continue; dfs(v, u, dep + 1, d, id); } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif // ONLINE_JUDGE int u, v; memset(belong, -1, sizeof(belong)); cin >> n; for(int i = 1; i <= n; i++) cin >> color[i]; vector<PII> I(n); for(int i = 1; i <= n - 1; i++) { cin >> u >> v; I[i] = make_pair(u, v); if(color[u] == color[v]) U(u, v); } set<int> node; for(int i = 1; i <= n - 1; i++) { u = F(I[i].first), v = F(I[i].second); node.insert(u); if(u == v) continue; node.insert(v); edge[u].insert(v); edge[v].insert(u); } int ans = 0, id; if(node.size() > 1) { dfs(F(1), -1, 0, ans, id); dfs(id, -1, 0, ans, id); ans = (ans + 1) >> 1; } cout << ans << endl; return 0; }