codeforces 734E-Anton and Tree

题目链接
哎，好久没更新博客了，从合肥回来之后感觉陷入了一种奇怪的状态，只想写题，不想写博客……从北京回来又被各种七七八八的事搞得很乱，先补上这一篇把，看了很长时间的缩点，也算是找个题练练手吧……虽然是用并查集缩的点……

题意：给你一棵树，每个节点只有黑白两色。每次可以选择一个节点，使得它与它相连（直接或间接）的所有相同颜色的点反色。问你至少要几次才能把所有节点变成一个颜色。

思路：一开始看，觉得这题就是个并查集裸题，把所有同色相连的并在一起，少的颜色有多少个块就多少次……然而这并不是最优解……如果一直对树直径终点进行操作，这样的操作次数是最少的。所以找出缩点后树的直径，除以二就是最终答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
int f[200005];
int find(int x)
{
	if(x==f[x])return x;
	 else return f[x]=find(f[x]);
}
void un(int x,int y)
{
	int a=find(x);
	int b=find(y);
	if(a==b)return ;
	 else 
	 {
	 	f[a]=b;
	 }
}
int col[200005];
int vis[200005];
int u[200005],v[200005];
vector<int >g[200005];
int ans=0;
int st;
void dfs(int u,int deep,int fa)
{
	//printf("u:%d deep:%d\n",u,deep);
	if(deep>ans)
	{
		ans=deep;
	    st=u;
	}
	int l=g[u].size();
	int rt=0;
	for(int i=0;i<l;i++)
	{
		if(g[u][i]==fa)continue;
		dfs(g[u][i],deep+1,u);
	}
    return;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=n;i++)scanf("%d",&col[i]);
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u[i],&v[i]);
		if(col[u[i]]==col[v[i]])
		{
			un(u[i],v[i]);
		}
	}
	for(int i=1;i<=n-1;i++)
	{
		if(col[find(u[i])]!=col[find(v[i])])
		{
			g[find(u[i])].push_back(find(v[i]));
			g[find(v[i])].push_back(find(u[i]));
		}
	}
	/*for(int i=1;i<=n;i++)
	 {
	 	printf("%d: ",i);
	 	for(int j=0;j<g[i].size();j++)
	 	 printf("%d ",g[i][j]);
	 	 printf("\n");
	  }*/ 
	dfs(find(1),1,-1);
	ans=0;
	dfs(st,1,-1);
	printf("%d\n",ans/2);
	return 0;
}