题目大意
给你一颗树，每个结点为黑色或白色。求一条路径，使得路径上距离为奇数的点颜色不同，距离为偶数的点颜色相同，输出这条路径最多能包含多少结点。
思路讲解
容易想到用树形动态规划搭配 dfs 解决。
将结点 1 1 1 设为根节点。设 d p i , 0 dp_{i,0} dpi,0 为以结点 i i i 为根节点的子树中，以 i i i 为起点的美丽路径最多包含多少个结点， d p i , 1 dp_{i,1} dpi,1 为以结点 i i i 为根节点的子树中，经过结点 i i i 却不以结点 i i i 为起点或终点的美丽路径最多包含多少个结点。
将
d
p
i
,
0
dp_{i,0}
dpi,0 的初始值设为
1
1
1。我们通过 dfs 搜索结点
i
i
i 的所有子结点，设当前搜索到的子节点为
j
j
j，如果
c
i
≠
c
j
c_i \ne c_j
ci=cj，则说明结点
i
i
i 可以连接到以结点
j
j
j 为起点的美丽路径上，
d
p
i
,
0
dp_{i,0}
dpi,0 就等于
max
(
d
p
i
,
0
,
1
+
d
p
j
,
0
)
\max(dp_{i,0},1+dp_{j,0})
max(dpi,0,1+dpj,0)。
对于 d p i , 1 dp_{i,1} dpi,1，容易发现，以结点 i i i 为根节点的子树中，不以 i i i 为起点或终点的美丽路径，其实就是用结点 i i i，将两条以它的颜色不同于它的子节点为起点的路径相连。而要想让其最长，只需取最大的两条即可。
我们可以给结点 i i i 的所有颜色不同于它的子节点 j j j 的 d p j , 0 dp_{j,0} dpj,0 从大到小进行排序，或放进一个大根堆中，取最大的两个相加再加 1 1 1 即可（前提是结点 i i i 要有至少 2 2 2 个颜色不同于它的子节点）。
答案为 max i = 1 n max ( d p i , 0 , d p i , 1 ) \max\limits_{i=1}^{n}\max(dp_{i,0},dp_{i,1}) i=1maxnmax(dpi,0,dpi,1)。
代码实现
#include <bits/stdc++.h>
using namespace std;
int n,c[100005],dp[100005][2],ans;
bool to[100005];
vector<int> g[100005];
void dfs(int x){
to[x]=1;//标记是否被访问过
int len=g[x].size();
dp[x][0]=1;//初始化为 1
priority_queue<int> q;
for(int i=0;i<len;i++)
if(!to[g[x][i]]){
dfs(g[x][i]);//要先进行 dfs
if(c[x]!=c[g[x][i]]){//如果颜色不同
dp[x][0]=max(dp[x][0],dp[g[x][i]][0]+1);
q.push(dp[g[x][i]][0]);
//赋值 dp[x][0] 并将其放入堆中
}
}
if(q.size()>1){
//如果数量大于 1，赋值 dp[x][1]
int last=q.top();
q.pop();
dp[x][1]=1+last+q.top();
}
ans=max(ans,max(dp[x][0],dp[x][1]));//统计答案
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
printf("%d",ans);
return 0;
}