#P17923. Tree and Subgraph Problem
Tree and Subgraph Problem
Tree and Subgraph Problem
题目描述
给定一棵有 个顶点的无根树,顶点 的颜色为 。
对于非空顶点集合 ,记 为树中包含 的最小连通子图。称顶点集合的有序对 合法,当且仅当:
- 均非空;
- 内所有顶点颜色相同, 内所有顶点颜色相同;两个集合的颜色不要求相同,也不要求不同;
- 与 没有公共顶点或边。
求合法有序对的数量,对 取模。 与 是不同的有序对。
输入格式
第一行一个整数 ,表示测试数据组数。每组数据:
第一行一个整数 。
第二行 个整数 。
接下来 行,每行两个整数 ,表示树的一条无向边。
输出格式
每组数据输出一行一个整数,表示答案对 取模的结果。
数据范围
- ,。
- ,,。
- 输入的边构成一棵树。
- 所有测试数据的 之和不超过 。
样例
3
2
1 1
1 2
5
1 1 1 2 2
1 2
2 3
3 4
4 5
5
1 2 1 2 1
1 2
1 3
2 4
2 5
2
54
42