题解：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;//初始化为 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;
}

原文地址：https://blog.csdn.net/andycode_/article/details/143752915

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！