……מלבד סוף טוב, מה עוד אפשר לבקש?
נתון עץ עם $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$ המכיל את כל הקשתות מצבע זה.