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

一道树状 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

，这分两种情况：

$x(\text{或 }y)=u$ 。注意这里的答案不能直接是 $d_u$ ，因为题面给定 $x\ne y$ ，所以我们要找到一个 $d$ 最大的儿子 $v$ ，答案即为 $s_u+d_v-2$ 。
$x\ne u\text{ 并且 }y\ne u$ 。这时由于 $x$ 和 $y$ 不能在同一棵子树内，所以我们就要在 $u$ 的所有儿子中找到 $d$ 最大的儿子 $v$ 和次大的儿子 $v'$ 。答案即为 $s_u+d_v+d_{v'}-4$ 。

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

代码

CPP

#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^)?
*/

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

文章操作

题意

思路

代码

相关推荐

评论

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