……นอกจากตอนจบที่สมบูรณ์แบบแล้ว คุณยังต้องการอะไรอีก?
กำหนดต้นไม้ที่มี $n$ โหนด โดยโหนดมีหมายเลขตั้งแต่ $1$ ถึง $n$ และมีโหนด $1$ เป็นราก สำหรับแต่ละ $i = 2, 3, \ldots, n$ จะมีเส้นเชื่อมสองทิศทางระหว่างโหนด $i$ กับโหนดพ่อ $p_i$ ของมัน โดยเส้นเชื่อมนี้มีสี $c_i$ และมีความยาว $w_i$
สำหรับสี $c$ ที่ปรากฏในต้นไม้ หากวิถีเชิงเดียว (simple path) วิถีหนึ่งผ่านเส้นเชื่อมที่มีสี $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$ เป็นจุดปลายด้านหนึ่ง ซึ่งประกอบด้วยเส้นเชื่อมทั้งหมดของสีนั้น