Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 1024 MB 총점: 100 난이도: [표시] 해킹 가능 ✓
통계

Gegeben ist ein Baum mit $n$ Knoten, wobei jeder Knoten entweder cyan oder weiß gefärbt ist. Für einen einfachen Pfad im Baum sei $c$ die Anzahl der cyanfarbenen Knoten und $w$ die Anzahl der weißen Knoten auf dem Pfad. Der Wert des Pfades beträgt $(c + w) - 2 \times |c - w|$, wobei $|c - w|$ der Absolutbetrag von $(c - w)$ ist.

Die Tiefe eines Knotens $u$ ist definiert als die Anzahl der Kanten auf dem kürzesten Pfad von Knoten $1$ zu Knoten $u$. Der Schlüsselknoten eines einfachen Pfades ist definiert als der Knoten mit der minimalen Tiefe unter allen Knoten auf diesem Pfad. Es lässt sich beweisen, dass der Schlüsselknoten eines einfachen Pfades eindeutig ist.

Berechnen Sie für jedes $1 \le i \le n$ den maximalen Wert unter allen einfachen Pfaden, deren Schlüsselknoten $i$ ist.

Zur Erinnerung: Ein Pfad im Baum ist eine nichtleere Folge von Knoten $p_1, p_2, \dots, p_k$, sodass jedes Paar benachbarter Knoten in dieser Folge durch eine Kante verbunden ist. Ein einfacher Pfad ist ein Pfad, in dem alle Knoten paarweise verschieden sind. Auch ein einzelner Knoten kann einen einfachen Pfad bilden.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^5$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die erste Zeile enthält eine ganze Zahl $n$ ($2 \le n \le 4 \times 10^5$), die die Anzahl der Knoten angibt.

Die zweite Zeile enthält eine 01-Zeichenkette der Länge $n$, die die Farbe jedes Knotens angibt. Ist das $i$-te Zeichen 0, so ist der $i$-te Knoten cyan gefärbt; andernfalls ist der $i$-te Knoten weiß gefärbt.

In den folgenden $(n - 1)$ Zeilen enthält die $i$-te Zeile zwei ganze Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le n$), die eine Kante zwischen den Knoten $u_i$ und $v_i$ angeben. Es wird garantiert, dass die gegebenen Kanten einen Baum bilden.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $4 \times 10^5$ nicht überschreitet.

Ausgabe

Geben Sie für jeden Testfall $n$ Zeilen aus, die jeweils eine ganze Zahl enthalten. Die $i$-te Zeile ist der maximale Wert unter allen einfachen Pfaden, deren Schlüsselknoten $i$ ist.

Beispiele

Hinweis

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.