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$,滿足序列入面每一對相鄰頂點之間都有一條邊相連。簡單路徑係指路徑入面所有頂點都互不相同嘅路徑。單一頂點都可以構成一條簡單路徑。

輸入格式

有唔少測試數據。輸入嘅第一行包含一個整數 $T$($1 \le T \le 10^5$),表示測試數據嘅數量。對於每組測試數據:

第一行包含一個整數 $n$($2 \le n \le 4 \times 10^5$),表示頂點嘅數量。

第二行包含一個長度為 $n$ 嘅 01 字串,表示每個頂點嘅顏色。如果第 $i$ 個字元係 0,則第 $i$ 個頂點係青色;否則,第 $i$ 個頂點係白色。

喺接下來嘅 $(n - 1)$ 行入面,第 $i$ 行包含兩個整數 $u_i$ 同 $v_i$($1 \le u_i, v_i \le n$),表示一條連接頂點 $u_i$ 同 $v_i$ 嘅邊。保證俾定嘅邊構成一棵樹。

保證所有測試數據嘅 $n$ 之和唔超過 $4 \times 10^5$。

輸出格式

對於每組測試數據輸出一共 $n$ 行,每行包含一個整數。第 $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.