Universal Cup Judging System

Universal Cup

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

On vous donne un arbre à $n$ sommets, dont chaque sommet est coloré soit en cyan, soit en blanc. Pour un chemin simple dans l'arbre, soient $c$ le nombre de sommets cyan et $w$ le nombre de sommets blancs sur ce chemin. La valeur du chemin est $(c + w) - 2 \times |c - w|$, où $|c - w|$ désigne la valeur absolue de $(c - w)$.

On définit la profondeur d'un sommet $u$ comme le nombre d'arêtes sur le plus court chemin entre le sommet $1$ et le sommet $u$. On définit le sommet clé d'un chemin simple comme étant le sommet de profondeur minimale parmi tous les sommets du chemin. On peut prouver que le sommet clé d'un chemin simple est unique.

Pour chaque $1 \le i \le n$, calculez la valeur maximale parmi tous les chemins simples dont le sommet clé est $i$.

Rappelons qu'un chemin dans l'arbre est une suite non vide de sommets $p_1, p_2, \dots, p_k$ telle que deux sommets consécutifs de cette suite soient toujours reliés par une arête. Un chemin simple est un chemin dont tous les sommets sont distincts. Un sommet seul peut également former un chemin simple.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 10^5$) indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient un entier $n$ ($2 \le n \le 4 \times 10^5$) indiquant le nombre de sommets.

La deuxième ligne contient une chaîne 01 de longueur $n$, indiquant la couleur de chaque sommet. Si le $i$-ème caractère est 0, le $i$-ème sommet est coloré en cyan ; sinon, le $i$-ème sommet est coloré en blanc.

Pour les $(n - 1)$ lignes suivantes, la $i$-ème ligne contient deux entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le n$), indiquant une arête reliant les sommets $u_i$ et $v_i$. Il est garanti que les arêtes données forment un arbre.

Il est garanti que la somme des $n$ sur l'ensemble des cas de test ne dépasse pas $4 \times 10^5$.

Sortie

Pour chaque cas de test, affichez $n$ lignes contenant chacune un entier. La $i$-ème ligne doit contenir la valeur maximale parmi tous les chemins simples dont le sommet clé est $i$.

Exemples

Remarque

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.