#P17912. Cyan White Tree

Cyan White Tree

题目描述

给定一棵 nn 个顶点的树,顶点编号为 11 至 nn,以顶点 11 为根。每个顶点为青色或白色。

一条简单路径可以只包含一个顶点,但不能为空。设路径上的青色顶点数为 cc,白色顶点数为 ww,它的价值为

c+w−2∣c−w∣.c+w-2|c-w|.

顶点深度是它到根的距离。路径中深度最小的顶点称为该路径的关键点;这个顶点是唯一的。

对于每个顶点 uu,求关键点恰好为 uu 的简单路径的最大价值。

输入格式

第一行是测试组数 TT。每组数据:

  • 第一行是 nn。
  • 第二行是长度为 nn 的二进制字符串,第 ii 个字符为 0 表示顶点 ii 为青色,为 1 表示白色。
  • 接下来 n−1n-1 行,每行给出一条无向边的两个端点。

输出格式

对每组数据输出 nn 行,第 ii 行是关键点为顶点 ii 的最大路径价值。答案可能为负数。

数据范围

1≤T≤1051\le T\le10^5,2≤n≤4×1052\le n\le4\times10^5;所有测试组的 nn 之和不超过 4×1054\times10^5。端点在 [1,n][1,n] 内,给出的边构成树。

样例

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