#P17912. Cyan White Tree
Cyan White Tree
题目描述
给定一棵 个顶点的树,顶点编号为 至 ,以顶点 为根。每个顶点为青色或白色。
一条简单路径可以只包含一个顶点,但不能为空。设路径上的青色顶点数为 ,白色顶点数为 ,它的价值为
顶点深度是它到根的距离。路径中深度最小的顶点称为该路径的关键点;这个顶点是唯一的。
对于每个顶点 ,求关键点恰好为 的简单路径的最大价值。
输入格式
第一行是测试组数 。每组数据:
- 第一行是 。
- 第二行是长度为 的二进制字符串,第 个字符为
0表示顶点 为青色,为1表示白色。 - 接下来 行,每行给出一条无向边的两个端点。
输出格式
对每组数据输出 行,第 行是关键点为顶点 的最大路径价值。答案可能为负数。
数据范围
,;所有测试组的 之和不超过 。端点在 内,给出的边构成树。
样例
3
8
00101110
1 2
1 3
3 4
3 5
5 6
5 7
7 8
2
01
1 2
2
00
1 2
6
-1
3
-1
1
-1
2
-1
2
-1
-1
-1