俾定一棵有 $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