简答题 偏难
#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的边。

保证输入的树中存在不同颜色的点。

输出格式

输出一个整数,代表相距最远的一对不同颜色节点的距离。


输入样例

5
0 1 0 1 0
1 2
1 3
3 4
3 5

输出样例

3

样例解释

相距最远的不同颜色的一对节点为节点 2 和 5。

数据范围

对于全部数据,保证有1≤n≤105,0≤ai≤1。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5+10; vector&lt;int&gt; 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&lt;2;j++){ if(far[x][j]!=-1&amp;&amp;far[i][j^1]!=-1){ ans = max(ans,far[x][j]-dep[x]+far[i][j^1]-dep[x]); } } for(int j=0;j&lt;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&gt;&gt;n; memset(far,-1,sizeof far); for(int i=1;i&lt;=n;i++){ cin&gt;&gt;col[i]; } for(int i=1;i&lt;n;i++){ int u,v; cin&gt;&gt;u&gt;&gt;v; g[u].push_back(v); g[v].push_back(u); } dfs(1,0); cout&lt;&lt;ans&lt;&lt;"\n"; }</pre>
解析

每个结点要么黑色要么白色,需要保存结点的颜色信息。选2个颜色不同的点,可以先枚举第1个点和第2个点,求他们的距离,再求最大值。任意2点都是连通的,能够相互访问,能求出最大值。根据数据范围,能得到部分分。另一种思路就是根据树的性质,答案的2个点假设是a和b,路径会经过他们的公共祖先,距离=公共祖先到a的距离+公共祖先到b的距离。每个点视为公共祖先的话,有可能是左孩子的黑色和右孩子的白色组合,也可能是左孩子的白色和右孩子的黑色组成,也可能只在左孩子或者右孩子中。所以,每个结点应该保留2种颜色的最远值。一次深搜即可。每个点访问1次,时间复杂度是O(n)。