...Ngoài một kết thúc viên mãn, bạn còn mong muốn điều gì nữa?
Cho một cây có $n$ đỉnh được đánh số từ $1$ đến $n$, có gốc tại đỉnh $1$. Với mỗi $i = 2, 3, \ldots, n$, giữa đỉnh $i$ và đỉnh cha $p_i$ của nó có một cạnh vô hướng có màu $c_i$ và độ dài $w_i$.
Đối với một màu $c$ xuất hiện trong cây, nếu một đường đi đơn đi qua tất cả các cạnh có màu $c$, hoặc không đi qua bất kỳ cạnh nào có màu $c$, thì màu $c$ được gọi là tốt đối với đường đi này; ngược lại, màu $c$ được gọi là xấu đối với đường đi này.
Cho một số nguyên $k \in \{0, 1\}$, hãy tìm độ dài lớn nhất của một đường đi đơn có số lượng màu xấu không vượt quá $k$. Độ dài của một đường đi được định nghĩa là tổng độ dài của tất cả các cạnh trên đường đi đó.
Bạn có thể chọn cùng một đỉnh làm hai đầu mút của đường đi; khi đó đường đi không đi qua cạnh nào và có độ dài bằng $0$.
Lưu ý rằng các cạnh cùng màu không nhất thiết liên thông, và độ dài của cạnh có thể bằng $0$.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $n, k$, lần lượt biểu thị số lượng đỉnh và giới hạn trên của số lượng màu xấu cho phép.
Dòng thứ $i$ trong $n - 1$ dòng tiếp theo chứa ba số nguyên $p_i, c_i, w_i$, biểu thị giữa đỉnh $i$ và đỉnh $p_i$ có một cạnh vô hướng có màu $c_i$ và độ dài $w_i$.
Dữ liệu ra
In ra một dòng chứa một số nguyên, biểu thị độ dài lớn nhất của một đường đi đơn có số lượng màu xấu không vượt quá $k$.
Ví dụ
Dữ liệu vào 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
Dữ liệu ra 1
108
Ghi chú
Chọn đường đi từ đỉnh $5$ đến đỉnh $6$, lần lượt đi qua các đỉnh $5, 1, 6$, có độ dài là $8 + 100 = 108$.
Đường đi này không đi qua cạnh nào có màu $1$ và đi qua toàn bộ các cạnh có màu $3$, do đó các màu $1, 3$ đều tốt. Nó chỉ đi qua một trong hai cạnh có màu $2$, do đó màu $2$ là xấu.
Đường đi này có đúng một màu xấu, thỏa mãn yêu cầu. Có thể chứng minh không tồn tại đường đi hợp lệ nào dài hơn.
Dữ liệu vào 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
Dữ liệu ra 2
35
Ghi chú
Chọn đường đi từ đỉnh $8$ đến đỉnh $9$, lần lượt đi qua các đỉnh $8, 4, 2, 1, 3, 6, 9$, có độ dài là $8 + 5 + 3 + 4 + 6 + 9 = 35$.
Đường đi này đi qua toàn bộ các cạnh của màu $1, 2, 5$ và không đi qua bất kỳ cạnh nào của màu $3, 4$, do đó không có màu xấu nào, thỏa mãn yêu cầu. Có thể chứng minh không tồn tại đường đi hợp lệ nào dài hơn.
Dữ liệu vào 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
Dữ liệu ra 3
16
Ghi chú
Chọn đường đi từ đỉnh $7$ đến đỉnh $8$, lần lượt đi qua các đỉnh $7, 2, 1, 3, 8$, có độ dài là $2 + 6 + 5 + 3 = 16$.
Đường đi này đi qua hai trong ba cạnh của màu $1$, do đó màu $1$ là xấu. Nó đi qua toàn bộ các cạnh của màu $3, 4$ và không đi qua cạnh nào của các màu khác, do đó có đúng một màu xấu, thỏa mãn yêu cầu.
Đường đi từ đỉnh $7$ đến đỉnh $9$ có độ dài là $17$, nhưng các màu $1, 2$ đều xấu nên không thỏa mãn yêu cầu. Có thể chứng minh không tồn tại đường đi hợp lệ nào có độ dài vượt quá $16$.
Giới hạn
Đối với tất cả dữ liệu, thỏa mãn:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- Với mỗi $i = 2, 3, \ldots, n$, có $1 \le p_i < i$, $1 \le c_i \le n$, $0 \le w_i \le 10^9$.
Nhiệm vụ con
Bài toán này sử dụng chấm theo nhóm (bundled testing) và có thiết lập phụ thuộc nhiệm vụ con hợp lý.
| Nhiệm vụ con | $n \le$ | $k =$ | Tính chất đặc biệt | Điểm |
|---|---|---|---|---|
| $1$ | $200$ | $0$ hoặc $1$ | Không | $5$ |
| $2$ | $3000$ | $0$ hoặc $1$ | Không | $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$ | Không | $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$ | Không | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | Không | $13$ |
- Tính chất đặc biệt A: Với mỗi màu, toàn bộ các cạnh của màu đó tạo thành một đồ thị con liên thông.
- Tính chất đặc biệt B: Mỗi màu xuất hiện nhiều nhất hai lần.
- Tính chất đặc biệt C: Với mỗi $i = 2, 3, \ldots, n$, $p_i$ được sinh ngẫu nhiên độc lập với xác suất đều từ các số nguyên $1, 2, \ldots, i - 1$.
- Tính chất đặc biệt D: Với mỗi màu, tồn tại một đường đi đơn có một đầu mút là đỉnh $1$ chứa toàn bộ các cạnh của màu đó.