Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.5 s Límite de memoria: 512 MB Puntuación total: 100
Estadísticas

זה לא עניין של כסף, זה עניין של העברת מסר.

ברשת של $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. אדם $1$ מעביר את הנייר לאדם $2$.
  2. אדם $2$ מתרגם את ההודעה משפה $3$ לשפה $4$.
  3. אדם $2$ מעביר את הנייר לאדם $3$.
  4. אדם $3$ מעביר את הנייר לאדם $4$.

לאדם $4$ יש כעת את ההודעה בשפה $4$, שאותה הוא מבין. המספר המינימלי של תורות הנדרש הוא ארבעה.

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.