……원만한 결말 외에, 당신이 또 무엇을 바라겠습니까?
$1$부터 $n$까지 번호가 매겨진 $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$가 주어집니다.
다음 $n - 1$개의 줄 중 $i$번째 줄에는 세 정수 $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$.
서브태스크
이 문제는 번들 테스트를 채택하고 있으며, 합리적인 서브태스크 의존성이 설정되어 있습니다.
| 서브태스크 번호 | $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$을 한 끝점으로 하고 해당 색깔의 모든 간선을 포함하는 단순 경로가 존재합니다.