【点分治练习】不虚就是要AK

2015年1月10日2,7755

【问题描述】

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)