Universal Cup Judging System

Universal Cup

Límite de tiempo: 1.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Cho một cây không gốc gồm $n$ đỉnh, bạn cần gán một trọng số đôi một khác nhau cho mỗi đỉnh, với các trọng số tạo thành một hoán vị của các số từ $1$ đến $n$.

Với mỗi phương án gán, ta xét tất cả các đường kính của cây (tức là đường đi đơn dài nhất trong cây). Trong số các đường kính này, ta chọn đường kính có dãy trọng số lớn nhất theo thứ tự từ điển (sắp xếp các trọng số của các đỉnh dọc theo đường đi theo thứ tự và so sánh theo thứ tự từ điển).

Mục tiêu của bạn là cực tiểu hóa thứ tự từ điển của dãy trọng số tương ứng với "đường kính lớn nhất theo thứ tự từ điển" này trong tất cả các phương án gán có thể.

Dữ liệu vào

Một bộ kiểm tra duy nhất chứa nhiều nhóm dữ liệu.

Dòng đầu tiên của dữ liệu vào là số lượng nhóm dữ liệu $T$ ($1 \le T \le 10^5$), biểu thị số nhóm dữ liệu trong bộ kiểm tra này.

Với mỗi nhóm dữ liệu, dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 2 \cdot 10^5$) cho biết số lượng đỉnh.

$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le n$), biểu thị một cạnh của cây.

Đảm bảo rằng trên tất cả các nhóm dữ liệu, $\sum n \le 2 \cdot 10^5$.

Kết quả

Với mỗi bộ dữ liệu, in ra một dòng gồm một số số nguyên biểu thị thứ tự từ điển nhỏ nhất có thể của đường kính có thứ tự từ điển lớn nhất.

Ví dụ

Dữ liệu vào

5
5
1 2
1 3
2 4
2 5
4
1 2
1 3
1 4
6
1 2
1 3
2 4
2 5
3 6
8
1 2
2 3
1 4
2 5
3 6
1 7
7 8
10
1 2
2 3
2 4
4 7
4 8
1 5
5 6
6 9
1 10

Kết quả

3 4 5 1
3 4 2
3 4 5 6 1
2 3 4 5 6 1
3 4 5 6 7 8 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.