#P17943. Embedding Trees
Embedding Trees
Embedding Trees
本题的子树和直径定义需要特别注意。
- 树 的大小为顶点数 。
- 顶点的度数是与它相连的边数。
- 一棵树 是 的子树,当且仅当 且 。这里的子树可以是任意非空连通子图,并不限于选定根后的某个完整根式子树。
- 记 为 的所有子树组成的集合。
- 树的直径定义为:所有最大度数不超过 的子树中,最大的顶点数。也就是最长简单路径的点数。
- 对正整数 ,在所有最大度数不超过 、直径恰好为 的树中,取大小最大的那些树,组成集合 。
- 定义 为满足 的最大正整数 ;若不存在这样的 ,则 。
给定一棵 个顶点的树 ,计算
两个子树不同,当且仅当顶点集合或边集合不同。
输入格式
第一行是测试用例数 ,。
每组用例第一行包含 。接下来 行,每行两个整数 ,表示树的一条边。
,,;所有用例的 。保证输入是一棵树。
输出格式
每组用例输出一行一个整数,表示所求和对 取模的结果。
样例 1
2
5
1 2
1 3
2 4
2 5
8
1 2
8 7
1 3
8 6
1 4
8 5
1 8
12
94
第一组样例共有17棵子树,其中5棵只有一个顶点、贡献为0,其余12棵的 值均为1。