题解：P11251 [GESP202409 八级] 美丽路径

题目传送门

题目大意

给你一颗树，每个结点为黑色或白色。求一条路径，使得路径上距离为奇数的点颜色不同，距离为偶数的点颜色相同，输出这条路径最多能包含多少结点。

思路讲解

容易想到用树形动态规划搭配 dfs 解决。

将结点 $1$ 设为根节点。设 $d{p}_{i,0}$ 为以结点 $i$ 为根节点的子树中，以 $i$ 为起点的美丽路径最多包含多少个结点，$d{p}_{i,1}$ 为以结点 $i$ 为根节点的子树中，经过结点 $i$ 却不以结点 $i$ 为起点或终点的美丽路径最多包含多少个结点。

将 $d{p}_{i,0}$ 的初始值设为 $1$。我们通过 dfs 搜索结点 $i$ 的所有子结点，设当前搜索到的子节点为 $j$，如果 $c_i\ne c_j$，则说明结点 $i$ 可以连接到以结点 $j$ 为起点的美丽路径上，$d{p}_{i,0}$ 就等于 $\max (d{p}_{i,0},1+d{p}_{j,0})$。

对于 $d{p}_{i,1}$，容易发现，以结点 $i$ 为根节点的子树中，不以 $i$ 为起点或终点的美丽路径，其实就是用结点 $i$，将两条以它的颜色不同于它的子节点为起点的路径相连。而要想让其最长，只需取最大的两条即可。

我们可以给结点 $i$ 的所有颜色不同于它的子节点 $j$ 的 $d{p}_{j,0}$ 从大到小进行排序，或放进一个大根堆中，取最大的两个相加再加 $1$ 即可（前提是结点 $i$ 要有至少 $2$ 个颜色不同于它的子节点）。

答案为 $\underset{i=1}{\overset{n}{\max }}\max (d{p}_{i,0},d{p}_{i,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;//初始化为 1priority_queue<int> q;for(int i=0;i<len;i++)if(!to[g[x][i]]){dfs(g[x][i]);//要先进行 dfsif(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;
}