CF734E Anton and Tree

題目連結：傳送門

給一棵每個點為黑色或白色n個節點的樹，一次操作可以使一個相同顔色的連通塊變成另一種顔色，求使整棵樹變成一種顔色的最少操作數

又是一道良心的E題

相同顔色相鄰的縮完點後

圖上相鄰節點的顔色一定不同

答案就是（樹的直徑+1）/2

/**
 * @Date:   2019-04-14T18:39:27+08:00
 * @Last modified time: 2019-04-14T18:39:28+08:00
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define A 1000010
#define B 2010

using namespace std;
typedef long long ll;
struct node {
    int next, to;
}e[A], e2[A];
int head[A], num, head2[A], num2;
void add(int fr, int to) {
    e[++num].next = head[fr];
    e[num].to = to;
    head[fr] = num;
}
void add2(int fr, int to) {
    e2[++num2].next = head2[fr];
    e2[num2].to = to;
    head2[fr] = num2;
}
int fa[A], n, m, a[A], b[A], col[A], vis[A], dis[A];
int find(int x) {
    if (fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}
void prepare(int fr, int faa) {
    vis[fr] = 1;
    for (int i = head[fr]; i; i = e[i].next) {
        int ca = e[i].to;
        if (ca == faa or vis[ca] or col[fr] != col[ca]) continue;
        int fx = find(ca), fy = find(fr); //注意哪邊往哪邊合
        if (fx != fy) fa[fx] = fy;
        prepare(ca, fr);
    }
}
void dfs(int fr, int faa) {
    for (int i = head2[fr]; i; i = e2[i].next) {
        int ca = e2[i].to;
        if (ca == faa) continue;
        dis[ca] = dis[fr] + 1;
        dfs(ca, fr);
    }
}

int main(int argc, char const *argv[]) {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> col[i], fa[i] = i;
    for (int i = 1; i < n; i++) cin >> a[i] >> b[i], add(a[i], b[i]), add(b[i], a[i]);
    for (int i = 1; i <= n; i++) if (!vis[i]) prepare(i, i);
    for (int i = 1; i <= n; i++)
        if (fa[a[i]] != fa[b[i]])
            add2(fa[a[i]], fa[b[i]]), add2(fa[b[i]], fa[a[i]]);
    int maxx = 0, pos = 1; dfs(1, 0);
    for (int i = 1; i <= n; i++) if (dis[i] > maxx) maxx = dis[i], pos = i;
    int ans = 0; memset(dis, 0, sizeof dis); dfs(pos, 0);
    for (int i = 1; i <= n; i++) ans = max(ans, dis[i]);
    cout << (ans + 1) / 2 << endl;
    return 0;
}