#P13678. [ARC130D] Zigzag Tree
[ARC130D] Zigzag Tree
题目描述
给定一棵有 个顶点的树。顶点编号为 到 ,第 条边连接顶点 和 。
请计算满足以下条件的正整数序列 的个数,并将结果对 取模。
- 如果 ,则
- 对于任意 ,如果顶点 和顶点 相邻,且顶点 和顶点 也相邻,则有 或 。
输入格式
输入以如下格式从标准输入读入。
输出格式
请输出答案。
输入输出样例 #1
输入 #1
3
1 2
2 3
输出 #1
4
输入输出样例 #2
输入 #2
4
1 2
1 3
1 4
输出 #2
12
输入输出样例 #3
输入 #3
6
1 2
2 3
3 4
4 5
5 6
输出 #3
122
输入输出样例 #4
输入 #4
9
8 5
9 8
1 9
2 5
6 1
7 6
3 8
4 1
输出 #4
19080
说明/提示
限制条件
- 输入的图是一棵树
样例解释 1
满足条件的 有以下 种:
由 ChatGPT 4.1 翻译