#P17886. Apple Tree
Apple Tree
给定一棵以 为根、含 个结点的树。它满足:每个非根结点的直接孩子数量严格小于其父结点的直接孩子数量。
一个方案是二元组 ,其中 为树上的结点, 是不含 的、大小为 的结点集合,并且存在整数 ,使所有 都满足 。距离定义为简单路径上的边数。
求方案数,答案对 取模。不同中心或不同集合算不同方案。 时每个中心对应一个空集方案。
输入格式
第一行是测试用例数 ,。
每组第一行两个整数 ,,。
第二行包含 ,其中 ,表示结点 的父亲。输入保证满足上述孩子数严格递减的条件。
所有测试用例的 之和不超过 。
输出格式
每组输出一个整数,表示方案数模 。
样例
3
3 3
1 1
5 2
1 1 2 3
6 3
1 1 1 2 2
1
20
16
第一组只有中心为 、集合为 的方案。