记录编号	379687	评测结果	AAAAAAAAEE
题目名称	Anton and Tree	最终得分	80
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	0.458 s
提交时间	2017-03-07 13:52:13	内存使用	13.55 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=4e5+10;
int n,c[N],w[N],next[N],head[N];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int ans,m[N],l[N];
void dfs(int x,int fa){
	for (int i=head[x];i;i=next[i])
	if (w[i]!=fa){
		dfs(w[i],x);
		m[w[i]]+=(c[x]!=c[w[i]]);
		if (m[x]<m[w[i]]) l[x]=m[x],m[x]=m[w[i]];
			else l[x]=max(l[x],m[w[i]]);
	}
	ans=max(ans,l[x]+m[x]);
}
int main()
{
	freopen("AntonandTree.in","r",stdin);
	freopen("AntonandTree.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&c[i]);
	for (int i=1;i<n;i++){
		int f,t;
		scanf("%d%d",&f,&t);
		add(f,t);add(t,f);
	}
	dfs(1,0);
	printf("%d\n",(ans+1)/2);
	return 0;
}