Universal Cup Judging System

Universal Cup

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

Cho một cây gồm $n$ đỉnh, mỗi đỉnh được tô màu xanh lơ (cyan) hoặc màu trắng. Đối với một đường đi đơn trên cây, gọi $c$ là số đỉnh màu xanh lơ và $w$ là số đỉnh màu trắng trên đường đi đó. Giá trị của đường đi là $(c + w) - 2 \times |c - w|$, trong đó $|c - w|$ là giá trị tuyệt đối của $(c - w)$.

Định nghĩa độ sâu của một đỉnh $u$ là số cạnh trên đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $u$. Định nghĩa đỉnh khóa của một đường đi đơn là đỉnh có độ sâu nhỏ nhất trong số tất cả các đỉnh trên đường đi đó. Có thể chứng minh rằng đỉnh khóa của một đường đi đơn là duy nhất.

Với mỗi $1 \le i \le n$, hãy tính giá trị lớn nhất trong số tất cả các đường đi đơn có đỉnh khóa là $i$.

Nhắc lại rằng một đường đi trên cây là một dãy đỉnh khác rỗng $p_1, p_2, \dots, p_k$ sao cho mỗi cặp đỉnh liên tiếp trong dãy được nối với nhau bởi một cạnh. Đường đi đơn là đường đi mà tất cả các đỉnh trên đó đều phân biệt. Một đỉnh đơn lẻ cũng có thể tạo thành một đường đi đơn.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của đầu vào chứa một số nguyên $T$ ($1 \le T \le 10^5$) cho biết số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:

Dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 4 \times 10^5$) cho biết số lượng đỉnh.

Dòng thứ hai chứa một xâu 01 có độ dài $n$, cho biết màu của từng đỉnh. Nếu ký tự thứ $i$ là 0, đỉnh thứ $i$ được tô màu xanh lơ; ngược lại, đỉnh thứ $i$ được tô màu trắng.

Trong $(n - 1)$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i$ và $v_i$ ($1 \le u_i, v_i \le n$), cho biết một cạnh nối hai đỉnh $u_i$ và $v_i$. Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây.

Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $4 \times 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, hãy in ra $n$ dòng, mỗi dòng chứa một số nguyên. Dòng thứ $i$ là giá trị lớn nhất trong số tất cả các đường đi đơn có đỉnh khóa là $i$.

Ví dụ

Ghi chú

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.