最远点对

题目描述

⼩杨有⼀棵包含 个节点的树，这棵树上的任意⼀个节点要么是⽩⾊，要么是⿊⾊。 ⼩杨想知道相距最远的⼀对不同颜⾊节点的距离是多少。

输入格式

第⼀⾏包含⼀个正整数 ，代表树的节点数。 第⼆⾏包含 个⾮负整数 （对于所有的 ，均有 等于 0 或 1），其中如果 ，则节点 的颜⾊为⽩⾊；如果 ，则节点 的颜⾊为⿊⾊。 之后 ⾏，每⾏包含两个正整数 ，代表存在⼀条连接节点 和 的边。 保证输⼊的树中存在不同颜⾊的点。

输出格式

输出⼀个整数，代表相距最远的⼀对不同颜⾊节点的距离。 3.1.4 样例1 1 5 2 0 1 0 1 0 3 1 2 4 1 3 5 3 4 6 3 5 1 3 3.1.5 样例解释 相距最远的不同颜⾊的⼀对节点为节点 和 。 3.1.6 数据范围 子任务编号 数据点占比 特殊条件 1 30% 树的形态为⼀条链 2 30% 3 40% 对于全部数据，保证有 ， 。 3.1.7 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 vector g[N]; 5 int col[N]; 6 int n; 7 int dep[N],far[N][2]; 8 int ans; 9 void dfs(int x,int fa){ 10 dep[x]=dep[fa]+1; 11 far[x][col[x]]=dep[x]; 12 for(int i:g[x]){ 13 if(i!=fa){ 14 dfs(i,x); 15 for(int j=0;j<2;j++){ 16 if(far[x][j]!=-1&&far[i][j^1]!=-1){ 17 ans = max(ans,far[x][j]-dep[x]+far[i][j^1]-dep[x]); 18 } 19 } 20 for(int j=0;j<2;j++){ 21 far[x][j]=max(far[x][j],far[i][j]); 22 } 23 } 24 } 25 ans = max(ans,far[x][col[x]^1]-dep[x]); 26 } 27 int main(){ 28 int n; 29 cin>>n; 30 memset(far,-1,sizeof far); 31 for(int i=1;i<=n;i++){ 32 cin>>col[i]; 33 } 34 for(int i=1;i<n;i++){ 35 int u,v; 36 cin>>u>>v; 37 g[u].push_back(v); 38 g[v].push_back(u); 39 } 40 dfs(1,0); 41 cout<<ans<<"\n"; 42 }

样例输入 #1

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

样例输出 #1

样例解释 #1

相距最远的不同颜⾊的⼀对节点为节点 和 。

数据范围

子任务编号 数据点占比 特殊条件 1 30% 树的形态为⼀条链 2 30% 3 40% 对于全部数据，保证有 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。