มันไม่เกี่ยวกับเรื่องเงิน แต่มันเกี่ยวกับการส่งข้อความต่างหาก
ในเครือข่ายของคน $n$ คนที่เชื่อมต่อกันด้วยโครงสร้างต้นไม้ คนที่ $1$ ต้องการส่งข้อความไปยังคนที่ $n$ มีภาษาที่แตกต่างกัน $10^9$ ภาษา ซึ่งมีหมายเลขตั้งแต่ $1$ ถึง $10^9$ คนที่ $i$ พูดภาษาทั้งหมดในช่วง $[l_i, r_i]$ ได้
คนที่ $1$ เริ่มต้นด้วยกระดาษแผ่นหนึ่งและสามารถเขียนข้อความเริ่มต้นด้วยภาษาใดก็ได้ที่เขาพูดได้ ในแต่ละเทิร์น คนที่ถือกระดาษอยู่ในขณะนั้นสามารถทำอย่างใดอย่างหนึ่งต่อไปนี้:
- ส่งกระดาษต่อไปให้คนที่อยู่ติดกันในต้นไม้
- หากเขาเข้าใจภาษาที่เขียนอยู่บนกระดาษในขณะนั้น เขาสามารถแปลเป็นภาษาอื่นใดก็ได้ที่เขาพูดได้ (โดยเขียนทับข้อความเดิม)
จงหาจำนวนเทิร์นน้อยที่สุดที่คนที่ $n$ จะได้รับกระดาษพร้อมข้อความที่เขียนด้วยภาษาที่เขาเข้าใจ
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม $n$ เพียงตัวเดียว — จำนวนคน
อีก $n - 1$ บรรทัดถัดมา แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองตัวคือ $u$ และ $v$ ซึ่งอธิบายเส้นเชื่อมระหว่างคนที่ $u$ และ $v$ ในต้นไม้
อีก $n$ บรรทัดถัดมา แต่ละบรรทัดประกอบด้วยจำนวนเต็มสองตัวคือ $l_i$ และ $r_i$ — ช่วงที่อธิบายภาษาที่คนที่ $i$ พูดได้
ข้อมูลส่งออก
พิมพ์จำนวนเต็มเพียงตัวเดียว — จำนวนเทิร์นน้อยที่สุดที่ต้องใช้เพื่อให้คนที่ $n$ ได้รับข้อความในภาษาที่เขาเข้าใจ
ข้อจำกัด
- $2 \le n \le 2 \cdot 10^5$,
- $1 \le u, v \le n$ สำหรับทุกเส้นเชื่อม,
- $u \neq v$ สำหรับทุกเส้นเชื่อม,
- $1 \le l_i \le r_i \le 10^9$,
- รับประกันว่าคนใดๆ สามารถส่งข้อความไปยังคนอื่นใดๆ ได้เสมอ (โดยอาจต้องผ่านการแปลหลายครั้ง)
ตัวอย่าง 1
4
1 2
2 3
3 4
1 3
2 4
3 5
4 6
4
หมายเหตุ
ในตัวอย่าง ต้นไม้เป็นเส้นทางสายเดียว
คนที่ $1$ พูดภาษา $1, 2, 3$ คนที่ $2$ พูดภาษา $2, 3, 4$ คนที่ $3$ พูดภาษา $3, 4, 5$ คนที่ $4$ พูดภาษา $4, 5, 6$
วิธีการที่เหมาะสมที่สุดวิธีหนึ่งเป็นดังนี้ ขั้นแรก คนที่ $1$ เขียนข้อความเป็นภาษา $3$ จากนั้นผู้คนจึงเริ่มผลัดกันทำเทิร์น:
- คนที่ $1$ ส่งกระดาษให้คนที่ $2$
- คนที่ $2$ แปลข้อความจากภาษา $3$ เป็นภาษา $4$
- คนที่ $2$ ส่งกระดาษให้คนที่ $3$
- คนที่ $3$ ส่งกระดาษให้คนที่ $4$
ตอนนี้คนที่ $4$ มีข้อความเป็นภาษา $4$ ซึ่งเขาเข้าใจแล้ว จำนวนเทิร์นน้อยที่สุดที่ต้องใช้คือสี่เทิร์น