#6172. Samjia 和大树
题目描述
Peter送给Samjia一颗大小为 的树， 节点编号从 到 。
Samjia要给树上的每一个节点赋一个 之间的权值， 并使得有边直接相连的两个节点的权值之差的绝对值 。
请你告诉Samjia有多少种不同的赋值方案。
只用求出答案对 取模得到的结果。
输入格式
输入数据的第一行包含一个整数 , 代表测试数据组数。
接下来是 组数据。
每组数据的第一行包含三个整数 , 和 。
接下来 n−1 行,每行包含两个整数 和 ，代表节点 和 之间有一条树边。
输出格式
对于每组数据， 输出一行， 包含一个整数， 代表所求的答案。
样例
样例输入
3
2 2 0
1 2
3 3 2
1 3
1 2
3 3 1
1 2
2 3样例输出
4
2
12数据范围与提示
对于所有数据，
| 测试点编号 | 特殊约定 | |
|---|---|---|
| 1,2 | 100 | 无 |
| 3,4 | 10000 | 无 |
| 5,6 | 第 号节点与 号节点直接相连 | |
| 7,8 | 第 号节点与第 号节点直接相连 | |
| 9,10 | 无 |
题目来源：fps-loj-small-pics.zip；FPS 共享题包，题包内第 185 题。保留原作者与原赛事署名。