问题2473--鸽子施工队2473: 鸽子施工队
时间限制: 10 Sec 内存限制: 256 MB
提交: 13 解决: 3
[提交] [状态] [讨论版] [命题人:]题目描述
鸽克多正在为他的国家规划一张设计图，在设计图上有n个城市(按1; 2; 3;……; n标号)，城市间共有n-1条道路，使得任意两个城市间都有路径可以互达。但不幸的是，每条道路的施工方可能会放鸽子，即在实际施工结束后，每条道路有0.5的概率无法投入使用，导致可能存在一些城市没有路径可以互达。定义每座城市的交通指数为从该城市出发，分别到其他可达的城市的最短路径长度之和（路径长度为经过的道路数量）。对于给出的一张设计图，鸽克多想知道按该设计图施工后所有城市的交通指数之和的期望。
输入
有多组输入数据，第一行一个整数T表示数据组数，对于每组数据，有n行。
每组数据第一行一个整数n表示城市数，接下来n-1行，每行两个整数u(1⩽ u⩽n)，v(1⩽v⩽n)，表示在该设计图上城市u和城市v之间有一条道路。
数据范围：1⩽n⩽105。
保证对于所有数据Σn⩽2×106。
输出
对于每组输入数据，输出一行一个整数，表示按该设计图施工后所有城市的交通指数之和的期望。
注意答案可以表示为一个分数P/Q, P、Q互质，且Q ≠0 mod (109 + 7)，你只需要输出P×Q-1 mod (109 + 7)。
（Q-1即Q对模109 + 7的逆元，即Q×Q-1 mod (109 + 7) = 1）。
样例输入
4
1
2
1 2
3
1 2
2 3
5
1 2
1 3
2 4
2 5
样例输出
0
1
3
500000013
提示
输入文件较大，不建议使用cin; cout，推荐使用scanf; printf
来源/分类
[提交] [状态]