Universal Cup Judging System

Universal Cup

시간 제한: 3.0 s 메모리 제한: 2048 MB 총점: 100 난이도: [표시] 해킹 가능 ✓
통계

พิกกี้ (ผู้ซึ่งใช้เวลาว่างบริหารคณะกรรมการโปรโตคอลการเชื่อมต่อระหว่างดวงดาว) กำลังเผชิญกับปัญหาฮาร์ดแวร์ที่ละเอียดอ่อน โครงข่ายการสื่อสารล่าสุดซึ่งประกอบด้วยสถานีทวนสัญญาณ $n$ สถานีที่เชื่อมต่อกันด้วยสายไฟเบอร์ออปติก $(n - 1)$ เส้นเป็นโครงสร้างต้นไม้ พร้อมสำหรับการติดตั้งใช้งานแล้วในที่สุด อย่างไรก็ตาม ระบบจะต้องถูกเปิดใช้งานด้วยความระมัดระวังอย่างยิ่ง

กระบวนการเปิดใช้งานเกี่ยวข้องกับการยิงพัลส์เลเซอร์ไปตามเส้นทางที่กำหนด เส้นทางถูกนิยามว่าเป็นเส้นทางเชิงเดียวที่ไม่ซ้ำกันระหว่างสองสถานี เนื่องจากความเสี่ยงร้ายแรงของ "การแทรกสอดไหลย้อนกลับเชิงควอนตัม" ซึ่งเป็นปรากฏการณ์ที่ทำให้ทีมทนายความของคณะกรรมการนอนไม่หลับในยามค่ำคืน จึงต้องปฏิบัติตามโปรโตคอลต่อไปนี้อย่างเคร่งครัด:

  • ต้องสร้างเส้นทางการส่งสัญญาณทีละเส้นทาง
  • เพื่อป้องกันไฟกระชาก เส้นทางที่สร้างขึ้นใหม่แต่ละเส้นทางสามารถใช้สถานีร่วมกับเซตของสถานีที่ถูกเปิดใช้งานไปแล้วโดยเส้นทางก่อนหน้าได้ อย่างมากหนึ่งสถานี

กล่าวอย่างเป็นทางการ ให้ $S$ เป็นเซตของสถานีที่ถูกเปิดใช้งานอยู่ในปัจจุบัน สำหรับเส้นทางใหม่ $P$ ใดๆ ที่ประกอบด้วยเซตของสถานี $V(P)$ เงื่อนไข $|V(P) \cap S| \le 1$ จะต้องเป็นจริง เมื่อยิงพัลส์ตามเส้นทางสำเร็จแล้ว สถานีทั้งหมดตามเส้นทางนั้นจะถือเป็นส่วนหนึ่งของเซตที่เปิดใช้งานแล้ว $S$

ภารกิจของคุณ หากคุณเลือกที่จะรับมัน คือการหาจำนวนพัลส์เลเซอร์น้อยที่สุดที่ต้องใช้เพื่อเปิดใช้งานทุกสถานีในโครงข่ายทั้งหมด และระบุลำดับของเส้นทางดังกล่าวหนึ่งลำดับเพื่อสร้างความพึงพอใจให้กับฝ่ายกฎหมาย

problem_16337_7ea995da1220bc7e6a98609de7d2cace.png
ภาพประกอบของชุดข้อมูลทดสอบตัวอย่างสองชุดแรก สังเกตว่าในกรณีที่ 2 พัลส์ที่สองใช้เพียงสถานี $2$ ร่วมกับพัลส์แรก ซึ่งเป็นไปตามกฎการไม่แทรกสอด

ข้อมูลนำเข้า

มีหลายชุดข้อมูลทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^4$) แสดงจำนวนชุดข้อมูลทดสอบ สำหรับแต่ละชุดข้อมูลทดสอบ:

บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ ($2 \le n \le 3 \times 10^5$) คือจำนวนสถานีในโครงข่าย

สำหรับ $(n - 1)$ บรรทัดถัดไป บรรทัดที่ $i$ ประกอบด้วยจำนวนเต็มสองจำนวน $u_i$ และ $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) อธิบายสายไฟเบอร์ออปติกสองทิศทางระหว่างสถานี $u_i$ และสถานี $v_i$

รับประกันว่าสายเชื่อมต่อทั้งหมดก่อตัวเป็นต้นไม้ และผลรวมของ $n$ จากทุกชุดข้อมูลทดสอบจะไม่เกิน $3 \times 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลจำนวนเส้นทางน้อยที่สุด $k$ ในบรรทัดแรก หลังจากนั้นให้แสดงผล $k$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองจำนวน $a_i$ และ $b_i$ แทนจุดปลายของเส้นทางที่ $i$ ในลำดับ สังเกตว่า $a_i$ อาจเท่ากับ $b_i$ ได้หากเส้นทางนั้นประกอบด้วยสถานีเพียงสถานีเดียว

หากมีลำดับที่เหมาะสมที่สุดหลายแบบ ลำดับใดก็ได้ที่ปฏิบัติตามโปรโตคอลการไม่แทรกสอดอย่างเคร่งครัดจะได้รับการยอมรับ

ตัวอย่าง

ข้อมูลนำเข้า

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

ข้อมูลส่งออก

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.