QOJ.ac

QOJ

Limite de temps : 2 s Limite de mémoire : 512 MB Points totaux : 100 Hackable ✓

#21438. Another Story END

Statistiques

……원만한 결말 외에, 당신이 또 무엇을 바라겠습니까?

$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$을 한 끝점으로 하고 해당 색깔의 모든 간선을 포함하는 단순 경로가 존재합니다.

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.