#P18472. Graph Partitioning 2
Graph Partitioning 2
Graph Partitioning 2
在成功解决《Cut Cut Cut!》之后,小青鱼想进一步提高划分图中连通块的能力。
有一天,一位神秘的智者给小青鱼一棵有 个顶点的无根树,以及一个整数 。令 为树的边集。小青鱼需要选择一个子集 ,删除 中的边,使剩下的每个连通块的顶点数均为 或 。
作为分割事物的大师,小青鱼轻松解决了这个问题。但智者想知道所有可能的结果:有多少种选择 的方式满足条件?如果选择的边子集不同,就视为不同方案。
请帮助小青鱼完成这项挑战。答案可能很大,只需输出它对 取模的结果。
输入格式
有多组测试数据。第一行一个整数 ,表示测试数据组数。对于每组测试数据:
第一行两个整数 (,),表示顶点数和较小的目标连通块大小。
接下来 行,每行两个整数 (),表示树的一条边。输入保证这些边构成一棵树。
保证同一输入文件所有测试数据的 之和不超过 。原题未另外给出 的上限;由 及总限制可推出 。
输出格式
对每组测试数据,输出一行一个整数,表示满足条件的边子集 的数量对 取模的结果。
样例
输入:
2
8 2
1 2
3 1
4 6
3 5
2 4
8 5
5 7
4 3
1 2
1 3
2 4
输出:
2
1
样例说明
以 表示连接顶点 的边。第一组数据的两个合法删除边集分别为 和 。