Universal Cup Judging System

Universal Cup

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

Gitt et tre med $n$ noder, der hver node er farget enten cyan eller hvit. For en enkel sti i treet, la $c$ være antallet cyanfargede noder og $w$ være antallet hvite noder på stien. Verdien til stien er $(c + w) - 2 \times |c - w|$, der $|c - w|$ er absoluttverdien av $(c - w)$.

Definer dybden til en node $u$ som antallet kanter på den korteste stien fra node $1$ til node $u$. Definer nøkkelnoden til en enkel sti som noden med minst dybde blant alle nodene på stien. Det kan bevises at nøkkelnoden for en enkel sti er unik.

For hver $1 \le i \le n$, beregn den maksimale verdien blant alle enkle stier som har $i$ som nøkkelnode.

Husk at en sti i treet er en ikke-tom sekvens av noder $p_1, p_2, \dots, p_k$ slik at hvert par av nabonoder i sekvensen er forbundet med en kant. En enkel sti er en sti der alle nodene er forskjellige. En enkelt node kan også utgjøre en enkel sti.

Inndata

Det er flere testtilfeller. Den første linjen av inndataen inneholder et heltall $T$ ($1 \le T \le 10^5$) som angir antallet testtilfeller. For hvert testtilfelle:

Den første linjen inneholder et heltall $n$ ($2 \le n \le 4 \times 10^5$) som angir antallet noder.

Den andre linjen inneholder en 01-streng med lengde $n$, som angir fargen til hver node. Hvis det $i$-te tegnet er 0, er den $i$-te noden farget cyan; ellers er den $i$-te noden farget hvit.

I de følgende $(n - 1)$ linjene inneholder den $i$-te linjen to heltall $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$), som angir en kant som forbinder nodene $u_i$ og $v_i$. Det er garantert at de oppgitte kantene danner et tre.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $4 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut $n$ linjer, der hver linje inneholder ett heltall. Den $i$-te linjen er den maksimale verdien blant alle enkle stier som har $i$ som nøkkelnode.

Eksempler

Merk

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.