「点分治练习」不虚就是要AK

2015年1月10日5,8555

「问题描述」

czy 很火,因为又有人说他虚了

为了证明他不虚,他决定要在这次比赛 AK

现在他正在和别人玩一个游戏:在一棵树上随机取两个点(两个点可以相同)

如果这两个点的距离是 4 的倍数,那么算 czy 赢,否则对方赢

现在 czy 想知道他能获胜的概率 以即约分数形式输出这个概率

(即”a/b” 的形式,其中 a 和 b 必须互质。如果概率为 1,输出”1/1”)

「输入格式」

多组数据,对于每组数据
第一行一个数 n,表示树上的节点个数
接下来 n-1 条边 a,b,c

描述 a 到 b 有一条长度为 c 的路径 当 n=0 时表示读入结束
数据组数不超过 10

「输出格式」

对于每组数据,输出一行,表示答案

「样例输入」

5

1 2 1

1 3 2

1 4 1

2 5 3

0

「样例输出」

7/25

「题解」

考虑过根的路径
记 f[x] 为前 S-1 棵子树长 (mod 4) 为 x 的路径数量 g[x] 为子树 S 长 (mod 4) 为 x 的路径数量
则 ans = 2∗∑t[d]∗t[(4−d)mod4]
复杂度 O(nlogn)

 

avatar
1 Comment threads
4 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
谢嘉东hzwer Recent comment authors
  Subscribe  
提醒
谢嘉东

这部分题目有哪里可以评测么?