题解：P12747 [POI 2016 R3] 巡游 Parade

SMHBD_ · 2025-10-29 15:24:45 · 题解

一道树状 DP。

题意

在树上找一条路径，使得路径上的每一个点连接的非路径边的数量最大。

转化一下，设一个点 u 出边数为 s_u，则要找的最大值变成一条路径所有点的 s 之和减去两倍的路径长度（因为路径上的每一条边会被算两次）。

思路

在把树的根设为 1 号点后，我们发现每一条路径都会有一个顶点（左右端点的 lca）。所以我们只用考虑对于每一个点，以它作为顶点的所有路径所能产生的最大答案。

想象一下，设当前考虑的点为 u，已知一条顶点为 u、左右端点为 x,y 的路径的答案 ans。我们把它的左端点扩至儿子 x'，则新路径的答案 ans'=ans+s_{x'}-2（右端点同理）。

我们定义 d_u 表示一条左端点为 u、右端点为 u 的后代（可以为本身）的路径的最大答案。显然，设 v 为它的儿子，则 d_u=\max(s_u,\sum \max(s_u+d_v-2))。

那么最终答案就很好求了。在找以点 u 为顶点的路径答案时，设路径的左右端点为 x,y，这分两种情况：

最后给找到的所有答案取最大值就行了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
long long n,d[maxn],ans;
vector<int> a[maxn];
void dfs(int u,int fa)
{
    long long max1=-1e9,max2=-1e9,s=a[u].size();
    //注意由于vector的size是unsigned long long类型的，要先转化成long long
    d[u]=a[u].size();
    for(int v:a[u])
    if(v!=fa)
    {
        dfs(v,u);
        d[u]=max(d[u],d[v]+s-2);
        if(d[v]-2>=max1)
        {
            max2=max1;
            max1=d[v]-2;
        }
        else if(d[v]-2>max2)max2=d[v]-2;
    }
    ans=max(ans,s+max1);
    ans=max(ans,s+max1+max2);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1,0);
    cout<<ans;
}
/*
!(^w^)?
*/