QOJ.ac

QOJ

시간 제한: 2 s 메모리 제한: 512 MB 총점: 100 해킹 가능 ✓

#21438. Another Story END

통계

...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 đó.

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.