QOJ.ac

QOJ

Límite de tiempo: 2 s Límite de memoria: 512 MB Puntuación total: 100 Hackeable ✓

#21438. Another Story END

Estadísticas

……מלבד סוף טוב, מה עוד אפשר לבקש?

נתון עץ עם $n$ צמתים הממוספרים מ-$1$ עד $n$, ששורשו בצומת $1$. עבור כל $i = 2, 3, \ldots, n$, ישנה קשת דו-כיוונית בין צומת $i$ לבין הורהו $p_i$ שצבעה $c_i$ ואורכה $w_i$.

עבור צבע $c$ המופיע בעץ, אם מסלול פשוט עובר דרך כל הקשתות מצבע $c$, או שאינו עובר דרך אף קשת מצבע $c$, נאמר שהצבע $c$ הוא טוב עבור מסלול זה; אחרת, נאמר שהצבע $c$ הוא רע עבור מסלול זה.

בהינתן מספר שלם $k \in \{0, 1\}$, מצאו את האורך המקסימלי של מסלול פשוט שיש בו לכל היותר $k$ צבעים רעים. אורך של מסלול מוגדר כסכום האורכים של כל הקשתות על המסלול.

ניתן לבחור את אותו צומת כשני קצות המסלול; במקרה זה, המסלול אינו עובר דרך אף קשת ואורכו $0$.

שימו לב שקשתות מאותו צבע אינן בהכרח קשירות, ואורך של קשת יכול להיות $0$.

קלט

השורה הראשונה מכילה שני מספרים שלמים $n, k$, המייצגים את מספר הצמתים ואת החסם העליון המותר למספר הצבעים הרעים, בהתאמה.

השורה ה-$i$ מתוך $n - 1$ השורות הבאות מכילה שלושה מספרים שלמים $p_i, c_i, w_i$, המציינים כי קיימת קשת דו-כיוונית בין צומת $i$ לצומת $p_i$ שצבעה $c_i$ ואורכה $w_i$.

פלט

הדפיסו שורה אחת המכילה מספר שלם אחד, המייצג את האורך המקסימלי של מסלול פשוט עם לכל היותר $k$ צבעים רעים.

דוגמאות

קלט 1

6 1
1 1 1
1 1 4
1 2 2
1 2 8
1 3 100

פלט 1

108

הערה

נבחר את המסלול מצומת $5$ לצומת $6$, העובר לפי הסדר דרך הצמתים $5, 1, 6$, ואורכו $8 + 100 = 108$.

מסלול זה אינו עובר דרך אף קשת מצבע $1$ ועובר דרך כל הקשתות מצבע $3$, ולכן הצבעים $1, 3$ שניהם טובים. הוא עובר רק דרך אחת משתי הקשתות מצבע $2$, ולכן צבע $2$ הוא רע.

למסלול זה יש בדיוק צבע רע אחד, ולכן הוא מקיים את הדרישה. ניתן להוכיח שלא קיים מסלול חוקי ארוך יותר.

קלט 2

10 0
1 1 3
1 2 4
2 1 5
2 3 40
3 2 6
3 4 2
4 5 8
6 5 9
7 3 10

פלט 2

35

הערה

נבחר את המסלול מצומת $8$ לצומת $9$, העובר לפי הסדר דרך הצמתים $8, 4, 2, 1, 3, 6, 9$, ואורכו $8 + 5 + 3 + 4 + 6 + 9 = 35$.

מסלול זה עובר דרך כל הקשתות מהצבעים $1, 2, 5$ ואינו עובר דרך אף קשת מהצבעים $3, 4$, ולכן אין בו צבעים רעים והוא מקיים את הדרישה. ניתן להוכיח שלא קיים מסלול חוקי ארוך יותר.

קלט 3

10 1
1 1 6
1 1 5
1 1 0
1 2 8
1 2 0
2 3 2
3 4 3
5 5 1
6 6 4

פלט 3

16

הערה

נבחר את המסלול מצומת $7$ לצומת $8$, העובר לפי הסדר דרך הצמתים $7, 2, 1, 3, 8$, ואורכו $2 + 6 + 5 + 3 = 16$.

מסלול זה עובר דרך שתיים משלוש הקשתות מצבע $1$, ולכן צבע $1$ הוא רע. הוא עובר דרך כל הקשתות מהצבעים $3, 4$ ואינו עובר דרך אף קשת מצבעים אחרים, ולכן יש לו בדיוק צבע רע אחד והוא מקיים את הדרישה.

אורך המסלול מצומת $7$ לצומת $9$ הוא $17$, אך הצבעים $1, 2$ שניהם רעים, ולכן הוא אינו מקיים את הדרישה. ניתן להוכיח שלא קיים מסלול חוקי שאורכו עולה על $16$.

מגבלות

עבור כל נתוני הבדיקה מתקיים:

  • $2 \le n \le 2 \times 10^5$;
  • $k \in \{0, 1\}$;
  • עבור כל $i = 2, 3, \ldots, n$, מתקיים $1 \le p_i < i$, $1 \le c_i \le n$ ו-$0 \le w_i \le 10^9$.

תתי-משימות

בעיה זו משתמשת בבדיקה מקובצת (bundled testing) עם תלויות סבירות בין תתי-המשימות.

תת-משימה $n \le$ $k =$ תכונה מיוחדת ניקוד
$1$ $200$ $0$ או $1$ ללא $5$
$2$ $3000$ $0$ או $1$ ללא $9$
$3$ $2 \times 10^5$ $0$ A $4$
$4$ $2 \times 10^5$ $0$ B $5$
$5$ $2 \times 10^5$ $0$ C $3$
$6$ $2 \times 10^5$ $0$ D $4$
$7$ $2 \times 10^5$ $0$ ללא $7$
$8$ $2 \times 10^5$ $1$ A $8$
$9$ $2 \times 10^5$ $1$ B $14$
$10$ $2 \times 10^5$ $1$ C $9$
$11$ $2 \times 10^5$ $1$ D $8$
$12$ $10^5$ $1$ ללא $11$
$13$ $2 \times 10^5$ $1$ ללא $13$
  • תכונה מיוחדת A: עבור כל צבע, כל הקשתות מצבע זה יוצרות תת-גרף קשיר.
  • תכונה מיוחדת B: כל צבע מופיע לכל היותר פעמיים.
  • תכונה מיוחדת C: עבור כל $i = 2, 3, \ldots, n$, הערך $p_i$ נבחר באופן בלתי תלוי ובאקראי בהתפלגות אחידה מתוך המספרים השלמים $1, 2, \ldots, i - 1$.
  • תכונה מיוחדת D: עבור כל צבע, קיים מסלול פשוט שאחד מקצותיו הוא צומת $1$ המכיל את כל הקשתות מצבע זה.

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.