专栏首页HansBug's Lab3522: [Poi2014]Hotel

3522: [Poi2014]Hotel

3522: [Poi2014]Hotel

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 253  Solved: 117

[Submit][Status][Discuss]

Description

有一个树形结构的宾馆,n个房间,n-1条无向边,每条边的长度相同,任意两个房间可以相互到达。吉丽要给他的三个妹子各开(一个)房(间)。三个妹子住的房间要互不相同(否则要打起来了),为了让吉丽满意,你需要让三个房间两两距离相同。 有多少种方案能让吉丽满意?

Input

第一行一个数n。 接下来n-1行,每行两个数x,y,表示x和y之间有一条边相连。

Output

让吉丽满意的方案数。

Sample Input

7 1 2 5 7 2 5 2 3 5 6 4 5

Sample Output

5

HINT

【样例解释】 {1,3,5},{2,4,6},{2,4,7},{2,6,7},{4,6,7}

【数据范围】 n≤5000

Source

By Dzy

题解:其实我感觉这个题更像是一个树状DP,可是想了半天似乎总是难以处理顶上的距离相等节点的问题(树状DP难免要把无根树用有根树的方式处理,这样子问题就来了)

其实正如很多网上的题解所言,枚举出每一个核心点(也就是三个点到此点距离相等,且三点来自核心点的不同子树上),然后根据外部各个子树的各个深度的点的统计,来计算出可能性的数量

于是这个里面涉及到对于一大堆数,怎样快速求出不同的数三三相乘的总和,比如(1,2,3,4),要求的就是\( 1 * 2 * 3 + 1 * 2 * 4 + 1 * 3 * 4 + 2 * 3 * 4 = 50 \)

其实这个东西可以仿照快速求出两两乘机和的办法——用O(n)的时间扫一遍,求出和,平方和,立方和,然后直接根据这三个数可以直接推出来—— \(\sum = {\frac{ {A_1}^{3}-3 A_2 A_1 +2 A_3}{6}}\)

然后别的没了,上代码

  1 /**************************************************************
  2     Problem: 3522
  3     User: HansBug
  4     Language: Pascal
  5     Result: Accepted
  6     Time:7828 ms
  7     Memory:3316 kb
  8 ****************************************************************/
  9  
 10 type
 11     point=^node;
 12     node=record
 13                g,w:longint;
 14                next:point;
 15     end;
 16     map=array[0..20000] of point;
 17 var
 18    i,j,k,l,m,n:longint;
 19    a,c:map;
 20    b:array[0..20000] of int64;
 21    d,e,f,g:array[0..20000] of longint;
 22    p:point;
 23    ans:int64;
 24 procedure add(x,y,z:longint;var a:map);
 25           var p:point;
 26           begin
 27                new(p);p^.g:=y;p^.w:=z;
 28                p^.next:=a[x];a[x]:=p;
 29           end;
 30 function cal:int64;
 31          var i:longint;a1,a2,a3:int64;
 32          begin
 33               a1:=0;a2:=0;a3:=0;
 34               if b[0]<3 then exit(0);
 35               for i:=1 to b[0] do
 36                   begin
 37                        a1:=a1+b[i];
 38                        a2:=a2+b[i]*b[i];
 39                        a3:=a3+b[i]*b[i]*b[i];
 40                   end;
 41               exit((a1*a1*a1-3*a1*a2+2*a3) div 6);
 42          end;
 43 procedure dfs(x,y:longint);
 44           var p:point;
 45           begin
 46                p:=a[x];g[x]:=1;
 47                while p<>nil do
 48                      begin
 49                           if g[p^.g]=0 then
 50                              begin
 51                                   inc(d[y+1]);
 52                                   dfs(p^.g,y+1);
 53                              end;
 54                           p:=p^.next;
 55                      end;
 56           end;
 57 begin
 58      readln(n);
 59      for i:=1 to n do a[i]:=nil;
 60      for i:=1 to n-1 do
 61          begin
 62               readln(j,k);
 63               add(j,k,1,a);add(k,j,1,a);
 64          end;
 65      ans:=0;
 66      for i:=1 to n do
 67          begin
 68               p:=a[i];
 69               for j:=1 to n do c[j]:=nil;
 70               fillchar(g,sizeof(g),0);
 71               g[i]:=1;
 72               while p<>nil do
 73                     begin
 74                          fillchar(d,sizeof(d),0);
 75                          d[1]:=1;
 76                          dfs(p^.g,1);
 77                          for j:=1 to n do
 78                              begin
 79                                   if d[j]=0 then break;
 80                                   add(j,d[j],0,c);
 81                              end;
 82                          p:=p^.next;
 83                     end;
 84               for j:=1 to n do
 85                   begin
 86                        b[0]:=0;
 87                        p:=c[j];
 88                        while p<>nil do
 89                              begin
 90                                   inc(b[0]);
 91                                   b[b[0]]:=p^.g;
 92                                   p:=p^.next;
 93                              end;
 94                        inc(ans,cal);
 95                   end;
 96  
 97               j:=0;
 98          end;
 99      writeln(ans);
100      readln;
101 end.                      

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2292: 【POJ Challenge 】永远挑战

    2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

    HansBug
  • 1131: [POI2008]Sta

    1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 783  Solved:...

    HansBug
  • 算法模板——sap网络最大流 2(非递归+邻接表)

    实现功能:同最大流 1 这里面主要是把前面的邻接矩阵改成了邻接表,相比之下速度大大提高——本人实测,当M=1000000 N=10000 时,暂且不考虑邻接矩阵...

    HansBug
  • 算法模板——计算几何2(二维凸包——Andrew算法)

    实现功能:求出二维平面内一对散点的凸包(详见Codevs 1298) 很神奇的算法——先将各个点按坐标排序,然后像我们所知的那样一路左转,求出半边的凸包,然后反...

    HansBug
  • 1601: [Usaco2008 Oct]灌水

    1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

    HansBug
  • 1015: [JSOI2008]星球大战starwar

    1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec  Memory Limit: 162 MB Submit: 3001...

    HansBug
  • 【kafka】kafka学习笔记(一)

    我们先看一下维基百科是怎么说的: Kafka是由Apache软件基金会开发的一个开源流处理平台,由Scala和Java编写。该项目的目标是为处理实时数据提供一...

    居士
  • 4052: [Cerc2013]Magical GCD

    4052: [Cerc2013]Magical GCD Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 148...

    HansBug
  • react组件性能优化探索实践

    React本身就非常关注性能,其提供的虚拟DOM搭配上Diff算法,实现对DOM操作最小粒度的改变也是非常的高效。然而其组件渲染机制,也决定了在对组件进行更新时...

    IMWeb前端团队
  • react组件性能优化探索实践

    React本身就非常关注性能,其提供的虚拟DOM搭配上Diff算法,实现对DOM操作最小粒度的改变也是非常的高效。然而其组件渲染机制,也决定了在对组件进行更新时...

    IMWeb前端团队

扫码关注云+社区

领取腾讯云代金券