[关闭]
@xiaoziyao 2020-10-01T14:44:31.000000Z 字数 3664 阅读 1021

SP6717 TWOPATHS - Two Paths解题报告

解题报告


SP6717 TWOPATHS - Two Paths解题报告

更好的阅读体验

题意

分析

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

1

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

中间可以用隔开,也可以用隔开。

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

我们可以枚举删除每一条边,然后每次做一遍树形dp,复杂度是的。

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


2

定义一些数组(可以先跳过,后面再回来看):

(命名有点毒瘤,不要介意QAQ)

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

我们分析一下点3(红点):

子树内直径(绿色路径),子树内不经过的最长链(棕色路径),决策点,子树内不经过且不在子树内的的最长链(灰色路径)。

子树内经过的最长链(橙色路径),决策点,子树内经过的次长链(紫色路径),决策点为,子树内经过的三长链(粉色路径)。

子树外直径(蓝色路径),以开始且在子树外的最长链(黄色路径)。


3

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

如何得出父亲为的结点子树内的直径

现在考虑如何求得子树外的直径

怎么求(即父亲子树外,且经过父亲的最长路径):

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

这样,答案就可以求出来了:

时间复杂度:

代码

需要注意的点:

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

  1. #include<stdio.h>
  2. const int maxn=100005,maxm=200005;
  3. int m,n,e;
  4. long long ans;
  5. int start[maxn],to[maxm],then[maxm];//链式前向星
  6. int ilen1[maxn],ilen2[maxn],ilen3[maxn],ilen1c[maxn],ilen2c[maxn],olen[maxn],idis[maxn],idis1[maxn],idis2[maxn],idis1c[maxn],odis[maxn];//上面有解释
  7. inline int max(int a,int b){
  8. return a>b? a:b;
  9. }
  10. inline long long lmax(long long a,long long b){
  11. return a>b? a:b;
  12. }
  13. inline void add(int x,int y){//加边
  14. then[++e]=start[x],start[x]=e,to[e]=y;
  15. }
  16. void dfs1(int x,int last){//第一遍dp,求ilen1,ilen2,ilen3,ilen1c,ilen2c,idis,idis1,idis2,idis1c
  17. for(int i=start[x];i;i=then[i]){
  18. int y=to[i];
  19. if(y==last)
  20. continue;
  21. dfs1(y,x);
  22. if(ilen1[x]<=ilen1[y]+1)//更新最长链
  23. ilen3[x]=ilen2[x],ilen2[x]=ilen1[x],ilen1[x]=ilen1[y]+1,ilen2c[x]=ilen1c[x],ilen1c[x]=y;
  24. else if(ilen2[x]<=ilen1[y]+1)//更新次长链
  25. ilen3[x]=ilen2[x],ilen2[x]=ilen1[y]+1,ilen2c[x]=y;
  26. else if(ilen3[x]<=ilen1[y]+1)//更新三长链
  27. ilen3[x]=ilen1[y]+1;
  28. if(idis1[x]<=idis[y])//更新idis1
  29. idis2[x]=idis1[x],idis1[x]=idis[y],idis1c[x]=y;
  30. else if(idis2[x]<=idis[y])//更新idis2
  31. idis2[x]=idis[y];
  32. }
  33. idis[x]=max(idis1[x],ilen1[x]+ilen2[x]);//注意,idis不仅可以从儿子的idis求得,也可以拼起来
  34. }
  35. void dfs2(int x,int last){//第二遍dp,求olen,odis
  36. for(int i=start[x];i;i=then[i]){
  37. int y=to[i];
  38. if(y==last)
  39. continue;
  40. olen[y]=olen[x]+1;//继承父亲的olen
  41. if(ilen1c[x]==y)//用最长链/次长链更新olen
  42. olen[y]=max(olen[y],ilen2[x]+1);
  43. else olen[y]=max(olen[y],ilen1[x]+1);
  44. odis[y]=odis[x];//继承父亲的odis
  45. //一个端点在父亲子树外,一个端点在父亲子树内
  46. if(ilen1c[x]==y)
  47. odis[y]=max(odis[y],olen[x]+ilen2[x]);
  48. else odis[y]=max(odis[y],olen[x]+ilen1[x]);
  49. //两个端点都在父亲子树内
  50. if(ilen1c[x]==y)
  51. odis[y]=max(odis[y],ilen2[x]+ilen3[x]);
  52. else if(ilen2c[x]==y)
  53. odis[y]=max(odis[y],ilen1[x]+ilen3[x]);
  54. else odis[y]=max(odis[y],ilen1[x]+ilen2[x]);
  55. //用父亲子树内现成的路径
  56. if(idis1c[x]==y)
  57. odis[y]=max(odis[y],idis2[x]);
  58. else odis[y]=max(odis[y],idis1[x]);
  59. dfs2(y,x);
  60. }
  61. }
  62. int main(){
  63. while(~scanf("%d",&n)){
  64. e=ans=0;
  65. for(int i=1;i<=n;i++)
  66. 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;
  67. for(int i=1;i<n;i++){
  68. int x,y;
  69. scanf("%d%d",&x,&y);
  70. add(x,y),add(y,x);
  71. }
  72. dfs1(1,0);
  73. dfs2(1,0);
  74. for(int i=2;i<=n;i++)
  75. ans=lmax(ans,1ll*idis[i]*odis[i]);
  76. printf("%lld\n",ans);
  77. }
  78. return 0;
  79. }

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注