#YDRG007E. 广义串并联图上邻域数点
广义串并联图上邻域数点
标题只是为了吸引你点进来的。
题目描述
有一棵 个点的树与 个集合 ,初始时 ,树上每个节点有一个权值 。
对于一个集合 与两个节点 而言,令 ,然后依次遍历树上 到 的简单路径经过的节点。假若遍历到的节点 ,那么让 ,否则让 。其中 表示赋值。将最后抵达节点 后 的值定义为 (此时节点 对 的改变已经完成),再定义一个集合的权值 $\text{val}(S) = \sum_{u \in S} \sum_{v \in {S \setminus u}} \text{cost}(S,u,v)$。
现在有 次事件。每次事件形如 u,v
,表示令 并删除集合 。
事件结束后,你需要回答 对 取模后的值,保证事件开始前集合 均未被删除。
输入格式
第 行共两个数 。
第 行,每行两个数 代表树上一条边。
第 行共 个数,分别表示 。
第 行,共 行,每行两个数 u,v
代表一次事件。
输出格式
共 行,表示对于每个事件回答,一行一个答案。
样例 #1
样例输入 #1
5 4
1 3
2 4
3 5
3 4
1 1 4 5 1
2 3
4 2
1 5
4 1
样例输出 #1
0
50
4294967292
166
样例 #2
样例输入 #2
10 9
2 1
3 2
4 2
5 1
6 5
7 5
8 6
9 7
10 8
24464 5705 28145 23281 16827 9961 491 2995 11942 4827
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
样例输出 #2
60338
244666
523800
991210
1591884
2152416
2869500
3682634
4577026
提示
本题开启子任务捆绑。
子任务编号 | 特殊性质 | 分值 |
---|---|---|
对于任意 满足 | ||
对于任意 保证满足 的 至多有 个 | ||
无特殊性质 |
对于 的数据,。