Universal Cup Judging System

Universal Cup

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

Givet ett träd med $n$ hörn är varje hörn färgat antingen cyan eller vitt. För en enkel väg i trädet, låt $c$ vara antalet cyanfärgade hörn och $w$ vara antalet vita hörn på vägen. Vägens värde är $(c + w) - 2 \times |c - w|$, där $|c - w|$ är absolutbeloppet av $(c - w)$.

Definiera djupet för ett hörn $u$ som antalet kanter på den kortaste vägen från hörn $1$ till hörn $u$. Definiera nyckelhörnet för en enkel väg som hörnet med minst djup bland alla hörn på vägen. Det kan visas att nyckelhörnet för en enkel väg är unikt.

För varje $1 \le i \le n$, beräkna det maximala värdet bland alla enkla vägar vars nyckelhörn är $i$.

Kom ihåg att en väg i trädet är en icke-tom följd av hörn $p_1, p_2, \dots, p_k$ sådan att varje par av intilliggande hörn i följden är förbundna med en kant. En enkel väg är en väg där alla hörn är olika. Ett enskilt hörn kan också utgöra en enkel väg.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 10^5$) som anger antalet testfall. För varje testfall:

Den första raden innehåller ett heltal $n$ ($2 \le n \le 4 \times 10^5$) som anger antalet hörn.

Den andra raden innehåller en 01-sträng av längd $n$, som anger färgen på varje hörn. Om det $i$-te tecknet är 0 är det $i$-te hörnet cyanfärgat; annars är det $i$-te hörnet vitt.

På de följande $(n - 1)$ raderna innehåller den $i$-te raden två heltal $u_i$ och $v_i$ ($1 \le u_i, v_i \le n$), vilket anger en kant som förbinder hörnen $u_i$ och $v_i$. Det garanteras att de givna kanterna bildar ett träd.

Det garanteras att summan av $n$ över alla testfall inte överstiger $4 \times 10^5$.

Utdata

För varje testfall, skriv ut $n$ rader som var och en innehåller ett heltal. Den $i$-te raden är det maximala värdet bland alla enkla vägar vars nyckelhörn är $i$.

Exempel

Notering

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.