美丽路径

题目描述

⼩杨有⼀棵包含 个节点的树，节点从 到 编号，并且每个节点要么是⽩⾊，要么是⿊⾊。 对于树上的⼀条简单路径（不经过重复节点的路径），⼩杨认为它是美丽的当且仅当路径上相邻节点的颜⾊均不相 同。例如下图，其中节点 和节点 是⿊⾊，其余节点是⽩⾊，路径 是美丽路径，⽽ 路径 不是美丽路径（相邻节点 和 颜⾊相同）。 对于树上的⼀条简单路径，⼩杨认为它的长度是路径包含节点的数量。⼩杨想知道最长的美丽路径的长度是多少。

输入格式

第⼀⾏包含⼀个正整数 ，代表节点数量。 第⼆⾏包含 个整数 ，代表每个节点的颜⾊，如果 ，代表节点 为⽩⾊，如果 ，代表节点 为⿊⾊。 之后 ⾏，每⾏包含两个正整数 ，代表存在⼀条连接节点 和节点 的边。

输出格式

输出⼀个整数，代表最长美丽路径的长度。 3.2.4 样例1 1 5 2 1 0 0 1 0 3 1 2 4 3 5 5 4 3 6 1 3 1 4 3.2.5 样例2 1 5 2 0 0 0 0 0 3 1 2 4 2 3 5 3 4 6 4 5 1 1 子任务编号 数据点占比 特殊条件 1 30% 树的形态是⼀条链 2 30% 3 40% 对于全部数据，保证有 ， ，同时保证给出的数据构成⼀棵树。 3.2.6 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 vector g[N]; 5 int dep[N],vis[N],c[N]; 6 int n,ans; 7 int dfs(int x,int fa){ 8 vis[x]=1; 9 dep[x]=dep[fa]+1; 10 int mx = dep[x]; 11 vector tmp; 12 tmp.push_back(mx); 13 for(auto i:g[x]){ 14 if(i==fa||c[i]==c[x])continue; 15 int d = dfs(i,x); 16 tmp.push_back(d); 17 mx = max(d,mx); 18 } 19 sort(tmp.begin(),tmp.end()); 20 int m = tmp.size(),res=1; 21 if(m>1){ 22 res = tmp[m - 1] + tmp[m - 2] - 2 * dep[x] + 1; 23 } 24 ans=max(ans,res); 25 return mx; 26 } 27 int main(){ 28 cin>>n; 29 for(int i=1;i<=n;i++){ 30 cin>>c[i]; 31 } 32 for(int i=1;i<n;i++){ 33 int u,v; 34 cin>>u>>v; 35 g[u].push_back(v); 36 g[v].push_back(u); 37 } 38 for(int i=1;i<=n;i++){ 39 if(!vis[i]){ 40 dfs(i,0); 41 } 42 } 43 cout<<ans<<"\n"; 44 }

样例输入 #1

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

样例输出 #1

样例输入 #2

1 5
2 0 0 0 0 0
3 1 2
4 2 3
5 3 4
6 4 5
1 1
子任务编号 数据点占比 特殊条件
1 30% 树的形态是⼀条链
2 30%
3 40%

样例输出 #2

数据范围

见题目描述

知识点与难度

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

测试点分布

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