Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Zorluk: [göster] Hack'lenebilir ✓
İstatistikler

Gefið er tré með $n$ hnútum þar sem hver hnútur er litaður annaðhvort blágrænn (cyan) eða hvítur. Fyrir einfaldan veg í trénu, látum $c$ vera fjölda blágrænna hnúta og $w$ vera fjölda hvítra hnúta á veginum. Gildi vegarins er $(c + w) - 2 \times |c - w|$, þar sem $|c - w|$ er algildi $(c - w)$.

Skilgreinum dýpt hnúts $u$ sem fjölda leggja á stysta veginum frá hnúti $1$ til hnúts $u$. Skilgreinum lykilhnút einfalds vegar sem hnútinn með minnsta dýpt meðal allra hnúta á veginum. Sanna má að lykilhnútur einfalds vegar er ótvírætt ákvarðaður.

Fyrir hvert $1 \le i \le n$ skal reikna hæsta gildið meðal allra einfaldra vega sem hafa $i$ sem lykilhnút.

Minnist þess að vegur í tré er ekki tóm runa hnúta $p_1, p_2, \dots, p_k$ þannig að sérhvert par aðliggjandi hnúta í rununni er tengt með legg. Einfaldur vegur er vegur þar sem allir hnútar eru ólíkir. Einn stakur hnútur getur einnig myndað einfaldan veg.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 10^5$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur heiltölu $n$ ($2 \le n \le 4 \times 10^5$) sem gefur til kynna fjölda hnúta.

Önnur línan inniheldur 01-streng af lengd $n$, sem gefur til kynna lit hvers hnúts. Ef $i$-ti stafurinn er 0, þá er $i$-ti hnúturinn blágrænn; annars er $i$-ti hnúturinn hvítur.

Í næstu $(n - 1)$ línum inniheldur $i$-ta línan tvær heiltölur $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$), sem táknar legg sem tengir hnútana $u_i$ og $v_i$. Tryggt er að gefnu leggirnir myndi tré.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $4 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal skrifa út $n$ línur, þar sem hver lína inniheldur eina heiltölu. $i$-ta línan er hæsta gildið meðal allra einfaldra vega sem hafa $i$ sem lykilhnút.

Dæmi

Athugasemd

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.