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

$n$개의 정점으로 이루어진 트리가 주어지며, 각 정점은 청록색(cyan) 또는 흰색(white)으로 칠해져 있습니다. 트리의 단순 경로에 대해, 경로에 포함된 청록색 정점의 개수를 $c$, 흰색 정점의 개수를 $w$라고 합시다. 이 경로의 가치는 $(c + w) - 2 \times |c - w|$이며, 여기서 $|c - w|$는 $(c - w)$의 절댓값입니다.

정점 $u$의 깊이를 정점 $1$에서 정점 $u$까지의 최단 경로에 있는 간선의 개수로 정의합니다. 단순 경로의 핵심 정점(key vertex)을 경로에 속한 모든 정점 중 깊이가 최소인 정점으로 정의합니다. 단순 경로의 핵심 정점은 유일함을 증명할 수 있습니다.

각 $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$)이 주어집니다.

두 번째 줄에는 각 정점의 색상을 나타내는 길이 $n$인 01-문자열이 주어집니다. $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.