[关闭]
@Junlier 2018-08-21T17:16:04.000000Z 字数 1757 阅读 1838

P2634 [国家集训队]聪聪可可(题解)(点分治)

图论——点分治
洛谷题目

  1. #include<iostream>
  2. #include<cstdlib>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<iomanip>
  7. #include<algorithm>
  8. #include<ctime>
  9. #include<queue>
  10. #include<stack>
  11. #include<vector>
  12. #define rg register
  13. #define il inline
  14. #define lst long long
  15. #define ldb long double
  16. #define N 20050
  17. using namespace std;
  18. const int Inf=1e9;
  19. int n,cnt,ans;
  20. int Max,tot,root;
  21. struct EDGE{
  22. int to,nxt,v;
  23. }ljl[N<<1];
  24. int hd[N];
  25. int size[N],vis[N];
  26. int dis[N],hh[3];
  27. il int read()
  28. {
  29. rg int s=0,m=0;rg char ch=getchar();
  30. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  31. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  32. return m?-s:s;
  33. }
  34. il void add(rg int p,rg int q,rg int o)
  35. {
  36. ljl[++cnt]=(EDGE){q,hd[p],o},hd[p]=cnt;
  37. }
  38. void get_root(rg int now,rg int fm)
  39. {
  40. size[now]=1;rg int num=0;
  41. for(rg int i=hd[now];i;i=ljl[i].nxt)
  42. {
  43. rg int qw=ljl[i].to;
  44. if(qw==fm||vis[qw])continue;
  45. get_root(qw,now);
  46. size[now]+=size[qw];
  47. num=max(num,size[qw]);
  48. }
  49. num=max(num,tot-size[now]);
  50. if(Max>num)Max=num,root=now;
  51. }
  52. void get_dis(rg int now,rg int fm)
  53. {
  54. hh[dis[now]%3]++;
  55. for(rg int i=hd[now];i;i=ljl[i].nxt)
  56. {
  57. rg int qw=ljl[i].to;
  58. if(qw==fm||vis[qw])continue;
  59. dis[qw]=dis[now]+ljl[i].v;
  60. get_dis(qw,now);
  61. }
  62. }
  63. il int Query(rg int now,rg int base)
  64. {
  65. rg int res=0;
  66. hh[0]=hh[1]=hh[2]=0;
  67. dis[now]=base;
  68. get_dis(now,0);
  69. res+=hh[0]*hh[0]+(hh[1]*hh[2]<<1);
  70. return res;
  71. }
  72. void divide(rg int now,rg int fm)
  73. {
  74. ans+=Query(now,0),vis[now]=1;
  75. rg int all=tot;
  76. for(rg int i=hd[now];i;i=ljl[i].nxt)
  77. {
  78. rg int qw=ljl[i].to;
  79. if(qw==fm||vis[qw])continue;
  80. ans-=Query(qw,ljl[i].v);
  81. tot=size[now]>size[qw]?size[qw]:all-size[qw];
  82. root=0,Max=Inf;
  83. get_root(qw,0);
  84. divide(root,0);
  85. }
  86. }
  87. il int gcd(rg int x,rg int y)
  88. {
  89. return y?gcd(y,x%y):x;
  90. }
  91. int main()
  92. {
  93. n=read();
  94. for(rg int i=1;i<n;++i)
  95. {
  96. rg int p=read(),q=read(),o=read();
  97. add(p,q,o),add(q,p,o);
  98. }
  99. Max=Inf,tot=n;
  100. get_root(1,0),divide(root,0);
  101. rg int GCD=gcd(ans,n*n);
  102. printf("%d/%d\n",ans/GCD,n*n/GCD);
  103. return 0;
  104. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注