#P6791. [2019福建夏令营]乙姬心恋爱宫殿

    ID: 6612 传统题 2000ms 1024MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-组合数学贡献法补集计数构造与建模交换求和顺序树算法虚树DFS 序排序补充相邻点 LCA栈建虚树树上倍增树上差分动态规划换根 DP数论模逆元CF2800

[2019福建夏令营]乙姬心恋爱宫殿

乙姬心恋爱宫殿

题目描述

给定一棵有 nn 个节点的树,第 ii 个节点的颜色为 cic_i,颜色编号在 11 到 qq 之间。

可以选择两个不同的同色节点作为端点,点亮它们之间的简单路径,包括两个端点。

求选择两条路径的方案数,要求两条路径没有任何公共节点。每条路径不区分方向,两条路径之间也不区分先后顺序。每条路径的两个端点必须同色,但两条路径使用的颜色可以不同。

此外,还有 mm 次询问。每次给出一个节点 kik_i,求在该节点不能作为任意一条路径的端点时,选择两条路径的方案数。该节点仍可以作为路径内部节点,各次询问相互独立。

所有答案对 109+710^9+7 取模。

输入格式

第一行三个整数 n,m,qn,m,q,分别表示节点数、询问数和颜色编号上界。qq 和颜色编号按完整正十进制整数读取;只需要比较颜色是否相等,未出现的颜色不影响答案。

第二行 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n。

接下来 n−1n-1 行,每行两个整数 ai,bia_i,b_i,表示树上的一条无向边。

接下来 mm 行,每行一个整数 kik_i,表示该次询问中不能作为端点的节点。

输出格式

输出 m+1m+1 行。

第一行输出没有任何端点限制时的方案数。之后 mm 行依次输出各次询问的方案数,均对 109+710^9+7 取模。

样例 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 ⁣→21\!\to2 与 3 ⁣→43\!\to4,答案为1;任意一点不能作为端点后,答案为0。

数据范围

所有数据满足 m≤n≤105m\le n\le10^5,1≤ci≤q1\le c_i\le q。

测试点编号 nn 的上界 数据特性
1、2 5050 无
3 10310^3 q=1q=1
4 10410^4
5 q=1q=1,m≤10m\le10
6 10310^3 m=1m=1
7、8 10410^4
9、10 q=2q=2,m≤10m\le10
11、12 10510^5 q=2q=2
13、14 10410^4 每种颜色的节点只询问一个
15、16 10510^5
17、18、19、20 无