……Бақытты соңынан басқа тағы не қалайсыз?
$1$-ден $n$-ге дейін нөмірленген $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$ берілген — сәйкесінше төбелер саны және рұқсат етілген жаман түстер санының жоғарғы шегі.
Келесі $n - 1$ жолдың $i$-ші жолында үш бүтін сан $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$.
Ішкі есептер
Бұл есепте топтастырылған тестілеу қолданылады және ішкі есептер арасында орынды тәуелділіктер орнатылған.
| Ішкі есеп нөмірі | $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$-төбе болатын және сол түстің барлық қырларын қамтитын қарапайым жол табылады.