Universal Cup Judging System

Universal Cup

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

נתון עץ עם $n$ קודקודים, כאשר כל קודקוד צבוע בציאן (תכלת) או בלבן. עבור מסלול פשוט בעץ, יהי $c$ מספר הקודקודים בצבע ציאן ויהי $w$ מספר הקודקודים הלבנים במסלול. ערך המסלול הוא $(c + w) - 2 \times |c - w|$, כאשר $|c - w|$ הוא הערך המוחלט של $(c - w)$.

נגדיר את העומק של קודקוד $u$ כמספר הקשתות במסלול הקצר ביותר מקודקוד $1$ לקודקוד $u$. נגדיר את קודקוד המפתח של מסלול פשוט כקודקוד בעל העומק המינימלי מבין כל הקודקודים במסלול. ניתן להוכיח שקודקוד המפתח של מסלול פשוט הוא יחיד.

עבור כל $1 \le i \le n$, חשבו את הערך המקסימלי מבין כל המסלולים הפשוטים שקודקוד המפתח שלהם הוא $i$.

נזכיר כי מסלול בעץ הוא סדרה לא ריקה של קודקודים $p_1, p_2, \dots, p_k$ כך שכל זוג קודקודים סמוכים בסדרה זו מחובר באמצעות קשת. מסלול פשוט הוא מסלול שבו כל הקודקודים שונים זה מזה. גם קודקוד בודד יכול להוות מסלול פשוט.

קלט

ישנם מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם $T$ ($1 \le T \le 10^5$) המציין את מספר מקרי הבדיקה. עבור כל מקרה בדיקה:

השורה הראשונה מכילה מספר שלם $n$ ($2 \le n \le 4 \times 10^5$) המציין את מספר הקודקודים.

השורה השנייה מכילה מחרוזת 01 באורך $n$, המציינת את הצבע של כל קודקוד. אם התו ה-$i$ הוא 0, הקודקוד ה-$i$ צבוע בציאן; אחרת, הקודקוד ה-$i$ צבוע בלבן.

ב-$(n - 1)$ השורות הבאות, השורה ה-$i$ מכילה שני מספרים שלמים $u_i$ ו-$v_i$ ($1 \le u_i, v_i \le n$), המציינים קשת המחברת בין הקודקודים $u_i$ ו-$v_i$. מובטח שהקשתות הנתונות יוצרות עץ.

מובטח שסכום ערכי ה-$n$ על פני כל מקרי הבדיקה אינו עולה על $4 \times 10^5$.

פלט

עבור כל מקרה בדיקה הדפיסו $n$ שורות, שכל אחת מהן מכילה מספר שלם אחד. השורה ה-$i$ היא הערך המקסימלי מבין כל המסלולים הפשוטים שקודקוד המפתח שלהם הוא $i$.

דוגמאות

הערה

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.