QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100 Hackable ✓

#21438. Another Story END

Statistics

……ماذا يمكن أن تتمنى أكثر من نهاية سعيدة؟

تُعطى شجرة تحتوي على $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.