1091 : เรียงบนต้นไม้ (treeinc)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)

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

งานของคุณ

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

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

    บรรทัดที่ 1 มีจำนวนเต็มบวก N (1≤N≤300,000) แทนจำนวนเมืองทั้งหมด
    บรรทัดที่ 2 ถึงบรรทัดที่ N จะบอกข้อมูลของถนน N-1 เส้นที่เชื่อมระหว่างเมืองสองเมือง โดยในแต่ละบรรทัดจะประกอบด้วยจำนวนเต็มสองจำนวน u,v หมายความว่ามีถนนที่เชื่อมระหว่างเมือง u กับเมือง v (1≤u,v≤N และ u≠v)

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

    มีจำนวนเต็มจำนวนเดียวบอกจำนวนเมืองในเส้นทางการเดินทางที่ยาวที่สุดที่สอดคล้องกับเงื่อนไขที่กำหนด (รวมทั้งเมืองต้นทางและเมืองปลายทางด้วย)

อธิบายข้อมูลน้ำเข้าและส่งออก

          หากเริ่มการเดินทางที่เมือง 1 และสิ้นสุดที่เมือง 8 จะเดินทางผ่านเมืองจำนวนมากที่สุดคือ 4 เมือง (รวมจุดเริ่มต้นและจุดสิ้นสุด) คือเมือง 1-2-6-8 ตามลำดับ

การให้คะแนน

    ชุดข้อมูลทดสอบมูลค่าไม่เกิน 40 คะแนน มีค่า N≤3,000 และในทุกชุดข้อมูลทดสอบมีค่า N≤300,000

โจทย์โดย: อาภาพงศ์ จันทร์ทอง
ที่มา: TOI.C:05-2009

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
9 1 2 2 9 1 7 6 8 2 6 3 9 4 9 5 4	4

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้