Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 2048 MB مجموع النقاط: 100 الصعوبة: [عرض] قابلة للهجوم ✓
الإحصائيات

Piggy (người mà trong thời gian rảnh rỗi điều hành Ủy ban Giao thức Kết nối Liên sao) đang phải đối mặt với một bài toán phần cứng hóc búa. Lưới truyền thông mới nhất, bao gồm $n$ trạm chuyển tiếp được kết nối bởi $(n - 1)$ đường cáp quang tạo thành cấu trúc cây, cuối cùng đã sẵn sàng để triển khai. Tuy nhiên, hệ thống phải được bật nguồn hết sức thận trọng.

Quá trình kích hoạt bao gồm việc bắn các xung laser dọc theo các đường đi cụ thể. Một đường đi được định nghĩa là tuyến đường đơn duy nhất giữa hai trạm. Do nguy cơ thảm khốc của "Giao thoa Dòng ngược Lượng tử" — một hiện tượng khiến các luật sư của ủy ban mất ngủ hằng đêm — giao thức sau đây phải được tuân thủ nghiêm ngặt:

  • Các đường truyền phải được thiết lập lần lượt từng đường một.
  • Để ngăn chặn xung điện tăng đột ngột, mỗi đường đi mới được thiết lập chỉ được phép có chung nhiều nhất một trạm với tập hợp các trạm đã được kích hoạt bởi bất kỳ đường đi nào trước đó.

Một cách hình thức, gọi $S$ là tập hợp các trạm hiện đã được kích hoạt. Với mọi đường đi mới $P$ gồm tập các trạm $V(P)$, điều kiện $|V(P) \cap S| \le 1$ phải được thỏa mãn. Khi một đường đi được bắn xung thành công, tất cả các trạm dọc theo đường đi đó được coi là một phần của tập đã kích hoạt $S$.

Nhiệm vụ của bạn, nếu bạn chọn chấp nhận nó, là xác định số lượng xung laser tối thiểu cần thiết để kích hoạt mọi trạm trong toàn bộ mạng lưới và đưa ra một dãy các đường đi như vậy để làm hài lòng bộ phận pháp lý.

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
Minh họa cho hai bộ dữ liệu mẫu đầu tiên. Lưu ý rằng trong Trường hợp 2, xung thứ hai chỉ có chung trạm $2$ với xung thứ nhất, thỏa mãn quy tắc không giao thoa.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^4$) cho biết số lượng bộ dữ liệu. 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 3 \times 10^5$), số lượng trạm trong mạng lưới.

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, u_i \neq v_i$), mô tả một đường cáp quang hai chiều giữa trạm $u_i$ và trạm $v_i$.

Đảm bảo rằng các đường liên kết tạo thành một cây và tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $3 \times 10^5$.

Kết quả

Với mỗi bộ dữ liệu, in ra số lượng đường đi tối thiểu $k$ trên dòng đầu tiên. Tiếp theo, in ra $k$ dòng, mỗi dòng chứa hai số nguyên $a_i$ và $b_i$, biểu diễn hai đầu mút của đường đi thứ $i$ trong dãy. Lưu ý rằng $a_i$ có thể bằng $b_i$ nếu đường đi chỉ gồm một trạm duy nhất.

Nếu có nhiều dãy tối ưu, bất kỳ dãy nào tuân thủ nghiêm ngặt giao thức không giao thoa đều được chấp nhận.

Ví dụ

Dữ liệu vào

3
3
1 2
2 3
5
1 2
2 3
2 4
2 5
7
1 2
1 3
2 4
2 5
3 6
3 7

Kết quả

1
1 3
2
4 5
1 3
3
7 7
1 6
4 5

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.