3522: [Poi2014]Hotel
3522: [Poi2014]Hotel
HansBug
发布于 2018-04-11 10:14:01
发布于 2018-04-11 10:14:01
3522: [Poi2014]Hotel
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 253 Solved: 117
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
题解：其实我感觉这个题更像是一个树状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. 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-04-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录