Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

$n$ 個の頂点からなる木が与えられます。各頂点はシアンまたは白のいずれかで塗られています。木上の単純パスについて、パスに含まれるシアンの頂点数を $c$、白の頂点数を $w$ とします。このパスの価値は $(c + w) - 2 \times |c - w|$ です。ここで、$|c - w|$ は $(c - w)$ の絶対値を表します。

頂点 $u$ の深さを、頂点 $1$ から頂点 $u$ への最短パスに含まれる辺の本数として定義します。単純パスのキー頂点を、そのパスに含まれるすべての頂点の中で深さが最小の頂点として定義します。単純パスのキー頂点は一意であることが証明できます。

各 $1 \le i \le n$ について、キー頂点が $i$ であるすべての単純パスの中での価値の最大値を求めてください。

なお、木上のパスとは、非空な頂点列 $p_1, p_2, \dots, p_k$ であって、列内で隣接する任意の 2 頂点が辺で結ばれているものを指します。単純パスとは、含まれる頂点がすべて相異なるパスです。単一の頂点も単純パスをなすことができます。

入力

複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す整数 $T$ ($1 \le T \le 10^5$) が与えられます。各テストケースについて:

1 行目には、頂点の個数を表す整数 $n$ ($2 \le n \le 4 \times 10^5$) が与えられます。

2 行目には、各頂点の色を表す長さ $n$ の 01 文字列が与えられます。$i$ 番目の文字が 0 のとき $i$ 番目の頂点はシアンで塗られており、そうでないとき $i$ 番目の頂点は白で塗られています。

続く $(n - 1)$ 行のうち $i$ 行目には、頂点 $u_i$ と $v_i$ を結ぶ辺を表す 2 つの整数 $u_i$ と $v_i$ ($1 \le u_i, v_i \le n$) が与えられます。与えられる辺が木をなすことが保証されています。

すべてのテストケースにおける $n$ の総和は $4 \times 10^5$ を超えないことが保証されています。

出力

各テストケースについて $n$ 行出力してください。各行には 1 つの整数を出力し、$i$ 行目にはキー頂点が $i$ であるすべての単純パスの中での価値の最大値を出力してください。

入出力例

注記

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.