社区讨论

【翻译】なめらかな木

OOhanaTyan
AT_ddcc2017_final_dなめらかな木参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lwhkj971
此快照首次捕获于
2024/05/22 16:34
2 年前
此快照最后确认于
2024/05/22 19:20
2 年前
查看原帖

题目翻译

给定 NN 个顶点的树，每个顶点编号为 1,2,…,N1,2,\dots,N。每个顶点上都写上整数 1,2,…,N1,2,\dots,N 中的数，顶点 ii 上写的数为 cic_i，不同顶点上写的数必须不同。
如果顶点 u,vu,v 邻接，也就是存在边 u,vu,v，那么必须满足 ∣cu−cv∣≤2|c_u-c_v|\le2。
满足上述条件的写数方案有多少种，请求出方案数模 1000000007=109+71000000007=10^9+7 的值。

数据范围

  • 1≤N≤501\le N\le 50
  • 1≤ai,bi≤N1\le a_i, b_i \le N
  • 可以保证输入构成一棵树

输入

输入按照以下格式。第一行输入一个 NN，下面的 N−1N-1 行，每行输入两个整数 aibia_i b_i，表示树中的一条边。

输出

如上，输出种类数模 109+710^9+7 的值。

测试用例

测试用例 1

输入
CPP
5
1 2 
1 3
1 4
1 5
输出
CPP
24
解说
顶点 11 只能写 33。

测试用例 2

输入
CPP
6
1 2
1 3
1 4
1 5
1 6
输出
CPP
0

测试用例 3

输入
CPP
4
1 2
2 3
3 4
输出
CPP
12

测试用例 4

输入
CPP
7
1 3
2 3
4 3
5 4
5 6
5 7
输出
CPP
48

回复

共 3 条回复，欢迎继续交流。

正在加载回复...