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