简答题
偏难
#21050
最远点对 题面描述 小杨有一棵包含n个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。 小杨想知道相距最远的一对不同颜色节点的距离是多少。 输入格式 第…
最远点对
题面描述
小杨有一棵包含n个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。
小杨想知道相距最远的一对不同颜色节点的距离是多少。
输入格式
第一行包含一个正整数 n,代表树的节点数。
第二行包含n个非负整数a1,a2,...,an(对于所有的1≤i≤n,均有ai等于0或1),其中如果ai=0,则节点i的颜色为白色;如果ai=1,则节点i的颜色为黑色。
之后n-1行,每行包含两个正整数xi,yi,代表存在一条连接节点xi和yi的边。
保证输入的树中存在不同颜色的点。
输出格式
输出一个整数,代表相距最远的一对不同颜色节点的距离。
输入样例
输出样例
样例解释
相距最远的不同颜色的一对节点为节点 2 和 5。
数据范围

对于全部数据,保证有1≤n≤105,0≤ai≤1。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int col[N];
int n;
int dep[N],far[N][2];
int ans;
void dfs(int x,int fa){
dep[x]=dep[fa]+1;
far[x][col[x]]=dep[x];
for(int i:g[x]){
if(i!=fa){
dfs(i,x);
for(int j=0;j<2;j++){
if(far[x][j]!=-1&&far[i][j^1]!=-1){
ans = max(ans,far[x][j]-dep[x]+far[i][j^1]-dep[x]);
}
}
for(int j=0;j<2;j++){
far[x][j]=max(far[x][j],far[i][j]);
}
}
}
ans = max(ans,far[x][col[x]^1]-dep[x]);
}
int main(){
int n;
cin>>n;
memset(far,-1,sizeof far);
for(int i=1;i<=n;i++){
cin>>col[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
cout<<ans<<"\n";
}</pre>
解析
每个结点要么黑色要么白色,需要保存结点的颜色信息。选2个颜色不同的点,可以先枚举第1个点和第2个点,求他们的距离,再求最大值。任意2点都是连通的,能够相互访问,能求出最大值。根据数据范围,能得到部分分。另一种思路就是根据树的性质,答案的2个点假设是a和b,路径会经过他们的公共祖先,距离=公共祖先到a的距离+公共祖先到b的距离。每个点视为公共祖先的话,有可能是左孩子的黑色和右孩子的白色组合,也可能是左孩子的白色和右孩子的黑色组成,也可能只在左孩子或者右孩子中。所以,每个结点应该保留2种颜色的最远值。一次深搜即可。每个点访问1次,时间复杂度是O(n)。