QOJ.ac

QOJ

実行時間制限: 2 s メモリ制限: 512 MB 満点: 100 ハック可能 ✓

#21438. Another Story END

統計

……Бақытты соңынан басқа тағы не қалайсыз?

$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$-төбе болатын және сол түстің барлық қырларын қамтитын қарапайым жол табылады.

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.