Codejam2014

2

ต้นไม้ก็คือกราฟที่ไม่มี cycle

ต้นไม้แบบมีราก คือการเลือกปมพิเศษขึ้นมาปมหนึ่ง และถือว่าปมนี้เป็นปมรากของต้นไม้ สำหรับสองปม x y ใด ๆ ที่มีเส้นเชื่อมระหว่างกัน เราจะถือว่า y เป็นลูกของ x ถ้า x อยู่ใกล้ปมรากมากกว่า y

ต้นไม้ไบนารี่แบบเต็ม (full binary tree) คือต้นไม้แบบมีรากที่ปมทุกปมมีลูก 2 ลูก หรือ 0 ลูกเสมอ

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

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

บรรทัดแรกของข้อมูลนำเข้าเป็นจำนวนเต็ม T ที่ระบุจำนวน test case ทั้งหมด โดยที่แต่ละ test case เป็นดังนี้ บรรทัดแรกมีจำนวนเต็ม N ซึ่งระบุจำนวนของปมในต้นไม้ หลังจากนั้นอีก N-1 บรรทัด แต่ละบรรทัดมีจำนวนเต็มสองตัวคือ xi และ yi ซึ่งระบุว่ามีเส้นเชื่อมแบบไม่มีทิศทางระหว่างปม xi และ yi

ข้อมูลส่งออก สำหรับแต่ละ test case ให้แสดงข้อมูลหนึ่งบรรทัดซึ่งมีข้อความ "Case #x: y" โดยที่ x คือหมายเลขของ test case (เริ่มต้นที่ 1) และ y คือจำนวนปมน้อยสุดที่ลบออกจาก G เพื่อทำให้เป็นต้นไม้ไบนารี่แบบเต็ม

ข้อจำกัด

1 <= T <= 100 1 <= xi, yi <= N

รับประกันว่าแต่ละ test case เป็นต้นไม้ที่ต่อถึงกันแน่นอน

ชุดข้อมูลทดสอบเล็ก 2 <= N <= 15

ชุดข้อมูลทดสอบใหญ่ 2 <= N <= 1000

อธิบายตัวอย่าง

ใน test case แรก G เป็นต้นไม้ไบนารี่แบบเต็มอยู่แล้ว ถ้าเราเลือกปม 1 เป็นราก ดังนั้นก็ไม่ต้องทำอะไร (ตอบ 0) ใน test case ที่สอง เราสามารถลบปม 3 และ 7 แล้วเลือกปม 2 เป็นรากของต้นไม้ไบนารี่แบบเต็มได้ ใน test case สุดท้าย เราสามารถลบปม 1 แล้วเลือกปม 3 เป็นรากของต้นไม้ไบนารี่แบบเต็มได้ (อีกกรณีหนึ่งคือเราสามารถลบปม 4 แล้วเลือก 2 เป็นรากก็ได้)

3

permutation ขนาด N เป็นลำดับของจำนวน N ตัว แต่ละตัวมีค่าระหว่าง 0 ถึง N-1 โดยที่แต่ละตัวปรากฏแค่หนึ่งครับ และสามารถปรากฏในลำดับใดก็ได้

มี permutation ขนาด N จำนวนมากมาย (มี N factorial แบบ แต่นั่นไม่จำเป็นสำหรับข้อนี้) บางทีเราต้องการสุ่มหยิบ permutation มาหนึ่งอัน และแน่นอนเราต้องการหยิบหนึ่งอันแบบ uniform (นั่นคือ ทุก ๆ permutation ขนาด N ต้องมีความน่าจะเป็นที่จะถูกเลือกเท่า ๆ กัน)

ด้านล่างเป็นโค้ดที่เป็นไปได้แบบหนึ่งที่จะทำงานนี้ (เราจะเรียกมันว่า good algorithm ต่อไป)

(ดูในโจทย์ภาษาอังกฤษ)

ในโค้ดด้านบน readint(a .. b) จะคืนค่าจำนวนเต็มที่สุ่มแบบ uniform จาก a ถึง b (รวม a และ b ด้วย)

นี่คืออัลกอริทึมนั้นถ้าอธิบายเป็นภาษาพูด: เราเริ่มที่ identity permutation จากนั้น for each k ตั้งแต่ 0 ถึง N-1 (inclusive) .....

นี่คือตัวอย่างสำหรับ N=4, เราเริ่มด้วย identity permutation:

0 1 2 3

(ดูต่อในโจทย์ภาษาอังกฤษ)

2 0 3 1

กระบวนการดังกล่าวจบลง และเราจะได้ random permutation

มีอัลกอริทึมอื่น ๆ อีกที่จะสร้าง random permutation อย่างไรก็ตาม มีอีกหลายอัลกอริทึมที่ดูคล้าย ๆ อัลกอริทึมด้านบน แต่ไม่ได้สร้าง random permutation ที่ uniform บาง permutation จะมีความน่าจะเป็นที่จะถูกสร้างมากกว่าอันอื่น

ด้านล่างเป็นอัลกอริทึมในกลุ่มดังกล่าว