@xiaoziyao
2020-10-01T14:44:31.000000Z
字数 3664
阅读 1021
解题报告
SP6717 TWOPATHS - Two Paths解题报告
神仙换根dp题,做了一个上午。
首先,不难发现两条不相交的链之间一定有一条边隔开,就像这两条链:
中间可以用隔开,也可以用隔开。
因为树上一条边一定对应着一对父子关系,因此我们可以把题意转化为:求哪一条边将树割成的两棵树直径乘积最大。
我们可以枚举删除每一条边,然后每次做一遍树形dp,复杂度是的。
这个复杂度可以通过弱化版:CF14D Two Paths。
定义一些数组(可以先跳过,后面再回来看):
(命名有点毒瘤,不要介意QAQ)
举个例子吧(图中添加了一些重边方便观看)
我们分析一下点3(红点):
子树内直径(绿色路径),子树内不经过的最长链(棕色路径),决策点,子树内不经过且不在子树内的的最长链(灰色路径)。
子树内经过的最长链(橙色路径),决策点,子树内经过的次长链(紫色路径),决策点为,子树内经过的三长链(粉色路径)。
子树外直径(蓝色路径),以开始且在子树外的最长链(黄色路径)。
我们用另一个角度解读题意:求所有点子树内的直径与子树外的直径乘积的最大值。
如何得出父亲为的结点子树内的直径:
现在考虑如何求得子树外的直径:
怎么求(即父亲子树外,且经过父亲的最长路径):
由于一定要经过,所以我们只需要讨论它的一个端点就好了。
这样,答案就可以求出来了:
时间复杂度:。
需要注意的点:
代码里加了一些注释方便理解。
#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