题意：给你一棵树， 每个点要么是黑色要么是白色， 有一种操作是将同一个颜色的连通块变成相反的颜色，问你最少变换几次， 整颗树变成一种颜色。

 

思路： 缩点， 加求树的直径， 答案为树的直径除二向上取整。

 

1 #include
     
       2 #define LL long long 3 #define mk make_pair 4 using namespace std; 5  6 const int N = 5e5 + 7; 7 const int inf = 0x3f3f3f3f; 8 const int INF = 0x3f3f3f3f3f3f3f3f; 9 10 int n, a[N], cnt[N], tot, vis[N], depth[N], id, ans;11 vector
      
        edge1[N], edge2[N];12 13 void dfs(int u, int pre, int op, int f) {14     vis[u] = f;15     for(int v : edge1[u]) {16         if(v == pre || a[v] != op)17             continue;18         dfs(v, u, op, f);19     }20 }21 22 void dfs2(int u, int pre, int deep) {23     depth[u] = deep;24     if(depth[u] > depth[id])25         id = u;26     for(int v : edge2[u]) {27         if(v == pre) continue;28         dfs2(v, u, deep + 1);29     }30 }31 32 void dfs3(int u, int pre, int deep) {33     ans = max(ans, deep);34     for(int v : edge2[u]) {35         if(v == pre) continue;36         dfs3(v, u, deep + 1);37     }38 }39 int main() {40     scanf("%d", &n);41     for(int i = 1; i <= n; i++) {42         scanf("%d", &a[i]);43     }44 45     for(int i = 1; i < n; i++) {46         int u, v; scanf("%d%d", &u, &v);47         edge1[u].push_back(v);48         edge1[v].push_back(u);49     }50 51     for(int i = 1; i <= n; i++) {52         if(vis[i]) continue;    53         dfs(i, 0, a[i], ++tot);54     }55 56     for(int u = 1; u <= n; u++) {57         for(int v : edge1[u]) {58             if(u > v || vis[u] == vis[v])59                 continue;60             edge2[vis[u]].push_back(vis[v]);61             edge2[vis[v]].push_back(vis[u]);62         }63     }64 65     dfs2(1, 0, 0);66     dfs3(id, 0, 0);67     if(ans & 1) ans++;68     printf("%d\n", ans / 2);69     return 0;70 }71 /*72 */