#P18043. The Symbolic Tree
The Symbolic Tree
The Symbolic Tree
题目描述
给定一棵有 个顶点的树,顶点编号为 ,以顶点 为根。你要在每个顶点上写一个非负整数,满足:
- 根上写的整数恰好为 ;
- 每个非根顶点上的整数不大于它父亲上的整数。
求合法填写方案数,对 取模。只要至少一个顶点上的整数不同,就认为两种方案不同。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 ,表示一条无向边。输入保证这些边构成一棵树。
,,。
输出格式
输出合法方案数对 取模的结果。
样例 1
输入:
5 1
1 2
1 3
3 4
3 5
输出:
10
样例 2
输入:
16 16
15 14
15 11
7 10
14 2
4 6
14 16
5 3
1 5
12 11
5 7
2 9
13 10
5 14
9 6
8 1
输出:
623173536