最远点对题解
前置芝士，树的直径：
可以先随便找一个点，进行深搜，找出距离最远的点。然后从找出的点再深搜一次，找出距离这个点最远的点，路径则为直径 （尝试证明失败）
也可以进行树形DP求解，即深搜一遍搜，一遍尝试组合直径，记录以这个点为根的子树的最长链的长度。
int dfs(int u,int fa){
int siz=0;
for(int i=0;i<e[u].size();i++){
int t=0;
if(e[u][i]!=fa)t=dfs(e[u][i],u)+1;
ans=max(siz+t,ans);
siz=max(siz,t);
}
return siz;
} 思路：
依照上方求直径的方法，我们先可以想到，如果可以找到一棵树的直径，又恰巧直径两端点颜色不同，答案一定是直径。
如果两端颜色相同，可以尝试仿照上面求直径的思路，即先随便从一个点开始，找到距离最远点，再找另一最远点。所以可以考虑到先是要求出直径的两点，然后再分别以两点为起点，找出分别距离它们最远的点且颜色与之不同，取最大值。
温馨提示：注意题目中说的距离是指一条链的长度减一
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005],sz[100005];//sz[i]从i点出发最远可以到达的长度
vector<int>e[100005];
int dfs(int u,int fa,int m){//m，-1表示对点的颜色不作要求
int ans=u;//ans为到当前点最远距离的点编号
if(a[u]==m||m==-1)sz[u]=1;
else sz[u]=-1e9;
for(int i=0;i<e[u].size();i++){
if(e[u][i]==fa)continue;
int w=dfs(e[u][i],u,m);
if(sz[e[u][i]]+1>sz[u])ans=w,sz[u]=sz[e[u][i]]+1;
}
return ans;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
int y=dfs(1,0,-1);//无论颜色的直径的第一个端点
for(int i=1;i<=n;i++)sz[i]=0;
int x=dfs(y,0,-1),sz1=sz[y];//另一端点和直径长度
for(int i=1;i<=n;i++)sz[i]=0;
if(a[y]!=a[x]){
cout<<sz1-1;
return 0;
}
int w1=dfs(y,0,(a[y]+1)%2),sz2=sz[y];
for(int i=1;i<=n;i++)sz[i]=0;
int w2=dfs(x,0,(a[x]+1)%2),sz3=sz[x];
cout<<max({sz2,sz3,0})-1;
return 0;
}