#P6791. [2019福建夏令营]乙姬心恋爱宫殿
[2019福建夏令营]乙姬心恋爱宫殿
乙姬心恋爱宫殿
题目描述
给定一棵有 个节点的树,第 个节点的颜色为 ,颜色编号在 到 之间。
可以选择两个不同的同色节点作为端点,点亮它们之间的简单路径,包括两个端点。
求选择两条路径的方案数,要求两条路径没有任何公共节点。每条路径不区分方向,两条路径之间也不区分先后顺序。每条路径的两个端点必须同色,但两条路径使用的颜色可以不同。
此外,还有 次询问。每次给出一个节点 ,求在该节点不能作为任意一条路径的端点时,选择两条路径的方案数。该节点仍可以作为路径内部节点,各次询问相互独立。
所有答案对 取模。
输入格式
第一行三个整数 ,分别表示节点数、询问数和颜色编号上界。 和颜色编号按完整正十进制整数读取;只需要比较颜色是否相等,未出现的颜色不影响答案。
第二行 个整数 。
接下来 行,每行两个整数 ,表示树上的一条无向边。
接下来 行,每行一个整数 ,表示该次询问中不能作为端点的节点。
输出格式
输出 行。
第一行输出没有任何端点限制时的方案数。之后 行依次输出各次询问的方案数,均对 取模。
样例 1 输入
6 6 2
2 1 2 1 2 2
1 2
1 3
2 4
2 5
2 6
1
2
3
4
5
6
样例 1 输出
2
0
1
0
1
1
1
其他样例
补充一个可直接验证的例子:4个点构成链,颜色全部相同。没有限制时只能选路径 与 ,答案为1;任意一点不能作为端点后,答案为0。
数据范围
所有数据满足 ,。
| 测试点编号 | 的上界 | 数据特性 |
|---|---|---|
| 1、2 | 无 | |
| 3 | ||
| 4 | ||
| 5 | , | |
| 6 | ||
| 7、8 | ||
| 9、10 | , | |
| 11、12 | ||
| 13、14 | 每种颜色的节点只询问一个 | |
| 15、16 | ||
| 17、18、19、20 | 无 |