题意：
给一颗树 每个节点有黑白2色
可以使一个色块同事变色，问最少的变色次数。
思路：
先缩点 把一样颜色的相邻点 缩成一个
然后新的树 刚好每一层是一个颜色。
最后的答案就是树的直径/2
不过我用的树上的dp，强行求了以每个点为根时树的深度
答案就是最小的深度-1
具体见代码：
const int maxn = 200000 + 10;int n;int color[maxn];int pa[maxn];vector<int> G[maxn], G2[maxn];void init(){scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", color + i);}int u, v;for (int i = 1; i < n; i++){scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}}int find(int x) { return pa[x] != x ? pa[x] = find(pa[x]) : x;}int fa[maxn];void getTree(){queue<int> q;q.push(1);color[0] = -1;while (!q.empty()){int u = q.front(); q.pop();if (color[fa[u]] == color[u]) pa[u] = find(fa[u]);else G2[fa[pa[u]]].push_back(u);for (int i = 0; i < G[u].size(); i++){int v = G[u][i];if (find(v) == find(fa[u])) continue;fa[v] = pa[u];q.push(v);}}swap(G, G2);}void pg(){cout << "Graph:" << endl;for (int i = 0; i <= n; i++){for (int j = 0; j < G[i].size(); j++){cout << i << " " << G[i][j] << endl;}}}int son1[maxn], son2[maxn]; //i节点的最大的儿子 和 次大的儿子的下标int deep[maxn]; int deepFa[maxn];//i的父亲除了i以外的最深深度int d[maxn];//以i为根时树的深度 d[i] = max(deep[i], deepFa[i] + 1)int dfs(int u) //得到每个节点最深儿子的深度{deep[u] = 0;for (int i = 0; i < G[u].size(); i++){int v = G[u][i];fa[v] = u;int tmp = dfs(v);if (tmp >= deep[u]){son2[u] = son1[u];son1[u] = v;deep[u] = tmp;}else{if (tmp > deep[son2[u]]) son2[u] = v;}}deep[u]++;return deep[u];}int bfs(){queue<int> q;for (int i = 0; i < G[1].size(); i++) q.push(G[1][i]);int ans = d[1] = deep[1];while (!q.empty()){int u = q.front(); q.pop();if (son1[fa[u]] == u) deepFa[u] = deep[son2[fa[u]]] + 1;else deepFa[u] = deep[son1[fa[u]]] + 1;deepFa[u] = max(deepFa[u], deepFa[fa[u]] + 1);d[u] = max(deep[u], deepFa[u] + 1);ans = min(ans, d[u]);for (int i = 0; i < G[u].size(); i++){q.push(G[u][i]);}}return ans - 1;}void solve(){for (int i = 1; i <= n; i++) pa[i] = i;getTree();memset(fa, -1, sizeof(fa));for (int i = 0; i <= n; i++) son1[i] = son2[i] = n + 1;dfs(0);cout << bfs() << endl;}int main(){init();solve();return 0;}
