220726 T1 树染色问题 （树的直径）

题目描述

高钧在校园中漫步时，经过了一棵树。这时，几个同学突然冒出来控制住了他。

这棵树有 nn 个节点， 每个节点有黑白两种颜色， 为了更好的 alb ， 需要把所有节点染成同一种颜色。

为了更好的戏耍高钧，高钧被告知如果他在最短的时间内把这棵树的所有节点染成同一种颜色， 那他就不会被 alb。

高钧每次操作可以将一个同色连通块染成另一种颜色，他想知道他最少需要几次操 作才能把这棵树的所有节点染成同一种颜色。

对于树上的一个点集 SS ， 它是这棵树的同色连通块当且仅当对于所有节点 i,j∈Si,j∈S，节点 ii 的颜色与节点 jj 的颜色相同且树上 ii 与 jj 简单路径上的所有点属于 SS 。

输入格式

第一行一个整数 nn 表示树的节点数。

第二行 nn 个整数 c_i∈ \{0,1 \}ci​∈{0,1} 表示第 ii 个节点的初始颜色。

接下来 n-1n−1 行，每行两个整数 a_i，b_iai​，bi​，表示树上的一条边。

输出格式

输出一行一个整数，表示最少的操作次数。

先将原图缩点，再找出新树的直径的中心，以他为根，答案就是直径长度除以2。

 1 #include <bits/stdc++.h>

 2 //#define loveGsy

 3 using namespace std;

 4 const int N = 2e5 + 10;

 5 vector<int> E[N];

 6 int n, T, rt;

 7 int col[N], d[N], a[N], b[N], bl[N];

 8 int read() {

 9     int x = 0, f = 1; char c = getchar();

10     while (c < '0'||c > '9') {if (c == '-') f = -1; c = getchar();}

11     while (c >= '0'&&c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();

12     return x * f;

13 }

14

15 void dfs(int u, int f) {

16     if (col[u] == col[f]) bl[u] = bl[f];

17     else bl[u] = ++T;

18     for (int i = 0; i < (int)E[u].size(); i++) {

19         int t = E[u][i];

20         if (t == f) continue;

21         dfs(t, u);

22     }

23 }

24

25 void dfs1(int u, int f) {

26     d[u] = d[f] + 1;

27     if (d[u] > d[rt]) rt = u;

28     for (int i = 0; i < (int)E[u].size(); i++) {

29         int t = E[u][i];

30         if (t == f) continue;

31         dfs1(t, u);

32     }

33 }

34

35 int main() {

36 #ifdef loveGsy

37     freopen("tree.in", "r", stdin);

38     freopen("tree.out", "w", stdout);

39 #endif

40     n = read();

41     for (int i = 1; i <= n; i++) col[i] = read();

42     for (int i = 1; i < n; i++) {

43         a[i] = read(), b[i] = read();

44         E[a[i]].push_back(b[i]); E[b[i]].push_back(a[i]);

45     }

46     col[0] = col[1] ^ 1;

47     dfs(1, 0);

48     for (int i = 1; i <= n; i++) E[i].clear();

49     for (int i = 1; i < n; i++) {

50         int x = bl[a[i]], y = bl[b[i]];

51         if (x != y) E[x].push_back(y), E[y].push_back(x);

52     }

53     dfs1(1, 0);

54     int x = rt; rt = 0;

55     dfs1(x, 0);

56     printf("%d\n", d[rt] / 2);

57     return 0;

58 }

220726 T1 树染色问题 （树的直径）的相关教程结束。