Universal Cup Judging System

Universal Cup

Límite de tiempo: 1 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

توجد $n$ مدن، مرقمة من 1 إلى $n$. وتوجد أيضاً $n - 1$ طرق ثنائية الاتجاه تربط بين هذه المدن، بحيث إنه لكل مدينتين $x$ و $y$ يوجد مسار من $x$ إلى $y$. يربط الطريق الـ $i$ بين المدينتين $u_i$ و $v_i$، وله تكلفة $c_i$. في كل مرة تمر فيها عبر الطريق $i$، تنفق $c_i$ عملة معدنية.

أنت الآن في المدينة 1 وتريد السفر لزيارة جميع المدن. في كل ثانية، إذا كنت في المدينة $x$، يمكنك اختيار مدينة $y$ متصلة مباشرة بالمدينة $x$ عبر طريق، والانتقال إلى المدينة $y$، ودفع تكلفة الطريق المقابل. يمكن المرور عبر كل طريق مرتين على الأكثر. عندما تكون قد زرت جميع المدن وأصبحت في المدينة 1، يمكنك إنهاء رحلتك. تكلفة الرحلة هي إجمالي تكلفة جميع التنقلات التي قمت بها.

يوجد أيضاً عدد صحيح $k$. أثناء رحلتك، يمكنك استخدام قسيمة مجانية مرة واحدة، مما يجعل تنقلاتك الـ $k$ التالية بلا تكلفة.

لكل $k$ من 0 إلى $2n - 2$، يجب عليك حساب أقل تكلفة لرحلة تزور جميع المدن وتستخدم القسيمة بشكل أمثل.

الإدخال

يحتوي السطر الأول على عدد صحيح واحد $t$ ($1 \le t \le 400$)، وهو عدد حالات الاختبار. لكل حالة اختبار:

يحتوي السطر الأول على عدد صحيح $n$ ($1 \le n \le 2000$)، يمثل عدد المدن.

تصف الأسطر الـ $n - 1$ التالية الطرق. يحتوي السطر الـ $i$ من هذه الأسطر على ثلاثة أعداد صحيحة $u_i$ و $v_i$ و $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$)، تمثل المدينتين المتصلتين بالطريق الـ $i$ وتكلفة ذلك الطريق.

يوجد مسار بين أي زوج من المدن. مجموع $n$ لا يتجاوز $2000$.

الإخراج

لكل حالة اختبار، اطبع سطراً واحداً يحتوي على $2n - 1$ عدداً صحيحاً: الإجابات لكل $k$ من 0 إلى $2n - 2$.

مثال

الإدخال

2
5
1 2 2
2 3 3
2 4 1
4 5 3
7
1 2 1
1 3 1
1 4 4
3 5 5
3 6 1
6 7 4

الإخراج

18 15 12 10 8 5 3 2 0
32 27 22 21 17 13 12 8 4 3 2 1 0

ملاحظة

في حالة الاختبار الأولى، يمكننا دائماً السفر على طول المسار $1, 2, 3, 2, 4, 5, 4, 2, 1$، بمتتالية التكاليف $2, 3, 3, 1, 3, 3, 1, 2$. المقاطع المعفاة من التكلفة لكل $k$ موضحة أدناه.

$k$ المقطع المجاني الإجابة
0 $[]$ 18
1 $[3]$ 15
2 $[3, 3]$ 12
3 $[2, 3, 3]$ 10
4 $[3, 3, 1, 3]$ 8
5 $[3, 3, 1, 3, 3]$ 5
6 $[2, 3, 3, 1, 3, 3]$ 3
7 $[2, 3, 3, 1, 3, 3, 1]$ 2
8 $[2, 3, 3, 1, 3, 3, 1, 2]$ 0

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.