SP6717 TWOPATHS - Two Paths解题报告

解题报告

SP6717 TWOPATHS - Two Paths解题报告

更好的阅读体验

题意

• 给定一棵$n$个点的树，求两条不相交的链长度乘积最大值
• 不相交指不同时经过某一个点，长度指边的个数
• $1\leqslant n\leqslant 10^5$

分析

神仙换根dp题，做了一个上午。

1

首先，不难发现两条不相交的链之间一定有一条边隔开，就像这两条链：

中间可以用$(5,6)$隔开，也可以用$(2,5)$隔开。

因为树上一条边一定对应着一对父子关系，因此我们可以把题意转化为：求哪一条边将树割成的两棵树直径乘积最大。

我们可以枚举删除每一条边，然后每次做一遍树形dp，复杂度是$O(n^2)$的。

这个复杂度可以通过弱化版：CF14D Two Paths。

2

定义一些数组（可以先跳过，后面再回来看）：

• $x$子树内直径为$idis_x$，$x$子树内不经过$x$的最长链为$idis1_x$（决策点为$idis1c_x$），$x$子树内不经过$x$且不在$idis1c_x$子树内的最长链为$idis2_x$（这个有点绕，下面会解释）；
• 以$x$开始且在$x$子树内的最长链长度为$ilen1_x$，同样限制的次长链和三长链长度分别为$ilen2_x,ilen3_x$此限制下最长链的决策点为$ilen1c_x$，次长链的决策点为$ilen2c_x$；
• $x$子树外直径为$odis_x$；
• 以$x$开始且在$x$子树外的最长链长度为$olen_x$。

（命名有点毒瘤，不要介意QAQ）

举个例子吧（图中添加了一些重边方便观看）

我们分析一下点3（红点）：

$3$子树内直径$idis_3=5$（绿色路径），子树内不经过$3$的最长链$idis1_3=2$（棕色路径），决策点$idis1c_3=4$，子树内不经过$3$且不在$idis1c_3$子树内的的最长链$idis2_3=1$（灰色路径）。

子树内经过$3$的最长链$ilen1_3=3$（橙色路径），决策点$ilen1c_3=4$，子树内经过$3$的次长链$ilen2_3=2$（紫色路径），决策点为$ilen2c_3=5$，子树内经过$3$的三长链$ilen3_3=1$（粉色路径）。

$3$子树外直径$odis_3=3$（蓝色路径），以$3$开始且在$3$子树外的最长链$olen_3=4$（黄色路径）。

3

我们用另一个角度解读题意：求所有点子树内的直径与子树外的直径乘积的最大值。

如何得出父亲为$f$的结点$x$子树内的直径$idis_x$：

• 树形dp求出最长链$ilen1_x$和次长链$ilen2_x$，将最长链和次长链拼起来；
• $x$子树内的直径也可以是子树内其他点子树内的直径$idis_y$。

现在考虑如何求得$x$子树外的直径$odis_x$：

• 若$odis_x$不在$f$子树内：如果某一条路径不在$f$子树内，那么一定不在$x$子树内，所以$odis_x$可以用父亲子树外的直径$odis_f$更新；
• 若$odis_x$在$f$子树内：在$f$子树内却不在$x$子树内的路径也可能成为$odis_x$，考虑$3$种情况。
• • 采用父亲子树内现成的路径$idis1_f$，但是如果这条路径在$x$子树内（即$idis1c_f=x$时）我们要采用不在$x$子树内最长的路径$idis2_x$；
• • 用父亲子树内的两条路径拼接，但注意一下这些路径不能经过$x$，因此我们需要用最长链，次长链，三长链组成，用这些路径的决策点来判断用哪两条路径；
• • 用父亲子树外的一条路径和父亲子树内的一条路径拼接，还是要注意$f$子树内的路径不能经过$x$。

怎么求$olen_x$（即父亲子树外，且经过父亲的最长路径）：

由于$olen_x$一定要经过$x$，所以我们只需要讨论它的一个端点就好了。

• 若端点不在$f$子树内：继承父亲$f$的$olen$，即$olen_x$可以用$olen_f+1$更新
• 若端点在$f$子树内：依照上面的方法，用最长链或次长链来更新$olen$。

这样，答案就可以求出来了：

时间复杂度：$O(n)$。

代码

需要注意的点：

• 开long long；
• 多组数据，记得清空；
• 转移时细节很多；
• 第一遍dp顺序为先儿子再父亲，第二遍dp顺序为先父亲再儿子。

代码里加了一些注释方便理解。

#include<stdio.h>
const int maxn=100005,maxm=200005;
int m,n,e;
long long ans;
int start[maxn],to[maxm],then[maxm];//链式前向星
int ilen1[maxn],ilen2[maxn],ilen3[maxn],ilen1c[maxn],ilen2c[maxn],olen[maxn],idis[maxn],idis1[maxn],idis2[maxn],idis1c[maxn],odis[maxn];//上面有解释
inline int max(int a,int b){
    return a>b? a:b;
}
inline long long lmax(long long a,long long b){
    return a>b? a:b;
}
inline void add(int x,int y){//加边
    then[++e]=start[x],start[x]=e,to[e]=y;
}
void dfs1(int x,int last){//第一遍dp，求ilen1,ilen2,ilen3,ilen1c,ilen2c,idis,idis1,idis2,idis1c
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        dfs1(y,x);
        if(ilen1[x]<=ilen1[y]+1)//更新最长链
            ilen3[x]=ilen2[x],ilen2[x]=ilen1[x],ilen1[x]=ilen1[y]+1,ilen2c[x]=ilen1c[x],ilen1c[x]=y;
        else if(ilen2[x]<=ilen1[y]+1)//更新次长链
            ilen3[x]=ilen2[x],ilen2[x]=ilen1[y]+1,ilen2c[x]=y;
        else if(ilen3[x]<=ilen1[y]+1)//更新三长链
            ilen3[x]=ilen1[y]+1;
        if(idis1[x]<=idis[y])//更新idis1
            idis2[x]=idis1[x],idis1[x]=idis[y],idis1c[x]=y;
        else if(idis2[x]<=idis[y])//更新idis2
            idis2[x]=idis[y];
    }
    idis[x]=max(idis1[x],ilen1[x]+ilen2[x]);//注意，idis不仅可以从儿子的idis求得，也可以拼起来
}
void dfs2(int x,int last){//第二遍dp，求olen,odis
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        olen[y]=olen[x]+1;//继承父亲的olen
        if(ilen1c[x]==y)//用最长链/次长链更新olen
            olen[y]=max(olen[y],ilen2[x]+1);
        else olen[y]=max(olen[y],ilen1[x]+1);
        odis[y]=odis[x];//继承父亲的odis
        //一个端点在父亲子树外，一个端点在父亲子树内
        if(ilen1c[x]==y)
            odis[y]=max(odis[y],olen[x]+ilen2[x]);
        else odis[y]=max(odis[y],olen[x]+ilen1[x]);
        //两个端点都在父亲子树内
        if(ilen1c[x]==y)
            odis[y]=max(odis[y],ilen2[x]+ilen3[x]);
        else if(ilen2c[x]==y)
            odis[y]=max(odis[y],ilen1[x]+ilen3[x]);
        else odis[y]=max(odis[y],ilen1[x]+ilen2[x]);
        //用父亲子树内现成的路径
        if(idis1c[x]==y)
            odis[y]=max(odis[y],idis2[x]);
        else odis[y]=max(odis[y],idis1[x]);
        dfs2(y,x);
    }
}
int main(){
    while(~scanf("%d",&n)){
        e=ans=0;
        for(int i=1;i<=n;i++)
            start[i]=ilen1[i]=ilen2[i]=ilen3[i]=ilen1c[i]=ilen2c[i]=olen[i]=idis[i]=idis1[i]=idis2[i]=idis1c[i]=odis[i]=0;
        for(int i=1;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y),add(y,x);
        }
        dfs1(1,0);
        dfs2(1,0);
        for(int i=2;i<=n;i++)
            ans=lmax(ans,1ll*idis[i]*odis[i]);
        printf("%lld\n",ans);
    }
    return 0;
}

码字/画图辛苦，点个赞吧QAQ