SP6717 TWOPATHS - Two Paths解题报告

· · 题解

SP6717 TWOPATHS - Two Paths解题报告

更好的阅读体验

题意

分析

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

1

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

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

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

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

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

2

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

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

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

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

子树内经过$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$。 这样，答案就可以求出来了： $$ans=max_{i=1}^n\{ilen_i\cdot olen_i\}$$ 时间复杂度：$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