[关闭]
@ysner 2018-08-12T01:27:44.000000Z 字数 2960 阅读 1930

[CF391E2]Three Trees

树形DP DP


题面

有三棵树,建两条边让他们相连,最大化所有点对距离之和。

解析

算法

似乎是怎么暴力怎么搞。
先预处理出三棵树内所有点对的距离和每一个点到其他点的距离和,然后枚举最后另两颗树接到哪棵树上。

接着举例推导两颗树相连时对答案新产生的贡献(考场上推了???)
设建的边两端点分别是点,对应树,大小为
点,对应树,大小为
边长为
则贡献为


(这是整道题的钥匙)

然后枚举另两棵树接在第三棵树的哪个点上,同时计算答案即可。
答案中要同时统计:(设,两树接到上)

都是直接套用上面的式子。
复杂度

算法

注意到似乎很傻逼。
可以换种思路,两次的树形解决。

第一次统计子树大小和子树所有点到根结点的距离之和
为父结点,为子结点。

第二次应用换根思想。
想一想若根变为儿子,原有的会怎么变化。
首先到个点的距离会全部
其次,每次往移,都需新加上结点的其他儿子及子树的贡献(子树外的贡献都被点统计过了)。
若设父亲加上的值为
则儿子加上的值为

于是预处理复杂度降到

接着发现枚举另两棵树接在第三棵树的哪个点上,是复杂度瓶颈。
但是,如设值最大的点为,那么可以猜出接一棵树在上面肯定不会不优(由那个式子决定)。
于是只要枚举另一棵树接在哪个结点上即可。
由于要现算,复杂度

注意下式子运算过程中是否乘爆。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<queue>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int N=2e5+100,inf=1e9;
  17. ll ans;
  18. struct Tree
  19. {
  20. int h[N],cnt,sz[N],pos,son[N],top[N],f[N];
  21. ll mx,tot[N],sum[N],dd,d[N],n;
  22. il Tree(){memset(h,-1,sizeof(h));cnt=0;pos=1;}
  23. struct Edge{int to,nxt;}e[N<<1];
  24. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;e[++cnt]=(Edge){u,h[v]};h[v]=cnt;}
  25. il void dfs1(re int u,re int fa)
  26. {
  27. sz[u]=1;f[u]=fa;d[u]=d[fa]+1;
  28. for(re int i=h[u];i+1;i=e[i].nxt)
  29. {
  30. re int v=e[i].to;
  31. if(v==fa) continue;
  32. dfs1(v,u);
  33. sz[u]+=sz[v];
  34. if(sz[v]>sz[son[u]]) son[u]=v;
  35. sum[u]+=sz[v]+sum[v];
  36. }
  37. }
  38. il void dfs2(re int u,re int up)
  39. {
  40. top[u]=up;
  41. if(son[u]) dfs2(son[u],up);
  42. for(re int i=h[u];i+1;i=e[i].nxt)
  43. {
  44. re int v=e[i].to;
  45. if(v==f[u]||v==son[u]) continue;
  46. dfs2(v,v);
  47. }
  48. }
  49. il void dfs3(re int u,re int fa,re ll las)
  50. {
  51. tot[u]=sum[u]+las;dd+=tot[u];
  52. if(tot[u]>mx) mx=tot[u],pos=u;
  53. for(re int i=h[u];i+1;i=e[i].nxt)
  54. {
  55. re int v=e[i].to;
  56. if(v==fa) continue;
  57. dfs3(v,u,las+n-sz[v]+sum[u]-sum[v]-sz[v]);
  58. }
  59. }
  60. il int LCA(re int u,re int v)
  61. {
  62. while(top[u]^top[v])
  63. {
  64. if(d[top[u]]<d[top[v]]) swap(u,v);
  65. u=f[top[u]];
  66. }
  67. return d[u]<d[v]?u:v;
  68. }
  69. il ll Dis(re int u,re int v){return d[u]+d[v]-2*d[LCA(u,v)];}
  70. }T[4];
  71. il void calc(re int A,re int B,re int C)
  72. {
  73. re ll s=(T[A].dd+T[B].dd+T[C].dd)+(T[A].mx*T[B].n+T[A].n*T[B].n+T[B].mx*T[A].n)+(T[C].mx*T[B].n+T[B].n*T[C].n+0)+(T[A].mx*T[C].n+0+T[C].mx*T[A].n),ysn=0;
  74. fp(i,1,T[B].n) ysn=max(ysn,T[B].tot[i]*T[C].n+(T[B].Dis(T[B].pos,i)+2)*T[A].n*T[C].n);
  75. ans=max(ans,s+ysn);
  76. }
  77. il ll gi()
  78. {
  79. re ll x=0,t=1;
  80. re char ch=getchar();
  81. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  82. if(ch=='-') t=-1,ch=getchar();
  83. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  84. return x*t;
  85. }
  86. int main()
  87. {
  88. T[1].n=gi();T[2].n=gi();T[3].n=gi();
  89. fp(i,1,T[1].n-1) T[1].add(gi(),gi());
  90. fp(i,1,T[2].n-1) T[2].add(gi(),gi());
  91. fp(i,1,T[3].n-1) T[3].add(gi(),gi());
  92. fp(i,1,3) T[i].dfs1(1,0),T[i].dfs2(1,1),T[i].dfs3(1,0,0),T[i].dd/=2;
  93. fp(i,1,3)
  94. fp(j,1,3)
  95. {
  96. if(i==j) continue;
  97. calc(i,j,6-i-j);
  98. }
  99. printf("%lld\n",ans);
  100. return 0;
  101. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注