#P18343. Black Red Tree
Black Red Tree
Black Red Tree
题目描述
给定一棵有 个顶点的树,顶点编号为 ,边按输入顺序编号为 。最初,所有边都是黑色。
接下来依次进行 次染色操作,第 次将编号为 的边染成红色。保证每条边恰好被染色一次,因此所有操作结束后,树中的边全部为红色。
每次操作后,求树中恰好经过 条黑边的简单路径数量。红边可以出现在路径中,但不计入黑边数量。路径不能重复经过边;从 到 与从 到 视为同一条路径,只统计一次。
本题的操作编号经过编码,你必须利用上一次的正确答案来解码下一次操作。
输入格式
每个输入文件只有一组测试数据。
第一行包含两个整数 。
接下来 行,第 行包含两个整数 ,表示第 条边连接顶点 和 。这些边构成一棵树。
接下来 行,第 行包含一个整数 。实际染色的边编号为
其中, 表示第 次染色后的答案。特别地, 是尚未进行任何染色、所有边均为黑色时的答案,并非固定为 。
保证解码后的 是 的一个排列。输入中的编码值 可以重复。
输出格式
输出 行,第 行输出一个整数 ,表示第 次染色后,恰好经过 条黑边的简单路径数量。
数据范围
- ;
- ;
- ;
- ;
- 输入边构成树,解码后的操作编号构成排列。
样例输入 1
6 1
4 6
4 2
4 3
5 6
1 2
4
2
1
2
3
样例输出 1
5
7
8
8
0
样例输入 2
6 2
4 6
4 2
4 3
5 6
1 2
2
5
5
4
3
样例输出 2
5
4
2
0
0
样例说明

第一组样例解码后的操作编号依次为 。上图左侧是前两次操作后的树,其中黑边用细线、红边用粗线表示。此时恰好包含一条黑边的路径为
$$1\to3,\quad1\to4,\quad2\to3,\quad2\to4,\quad 3\to6,\quad4\to6,\quad5\to6,$$共 条。
第二组样例解码后的操作编号依次为 。上图右侧是前三次操作后的树。此时恰好包含两条黑边的路径只有 和 ,共 条。