QOJ.ac

QOJ

حد الوقت: 2 s حد الذاكرة: 512 MB مجموع النقاط: 100 قابلة للهجوم ✓

#21438. Another Story END

الإحصائيات

...¿Qué más podrías desear, aparte de un final feliz?

Se te da un árbol con $n$ vértices numerados del $1$ al $n$, con raíz en el vértice $1$. Para cada $i = 2, 3, \ldots, n$, hay una arista bidireccional entre el vértice $i$ y su padre $p_i$ con color $c_i$ y longitud $w_i$.

Para un color $c$ que aparece en el árbol, si un camino simple pasa por todas las aristas de color $c$, o no pasa por ninguna arista de color $c$, entonces se dice que el color $c$ es bueno para este camino; de lo contrario, se dice que el color $c$ es malo para este camino.

Dado un entero $k \in \{0, 1\}$, halla la longitud máxima de un camino simple con a lo sumo $k$ colores malos. La longitud de un camino se define como la suma de las longitudes de todas las aristas en el camino.

Puedes elegir el mismo vértice como ambos extremos del camino; en este caso, el camino no pasa por ninguna arista y tiene longitud $0$.

Ten en cuenta que las aristas del mismo color no necesariamente son conexas, y la longitud de una arista puede ser $0$.

Entrada

La primera línea contiene dos enteros $n, k$, que representan el número de vértices y el límite superior permitido de colores malos, respectivamente.

La $i$-ésima de las siguientes $n - 1$ líneas contiene tres enteros $p_i, c_i, w_i$, indicando que hay una arista bidireccional entre el vértice $i$ y el vértice $p_i$ de color $c_i$ y longitud $w_i$.

Salida

Imprime una sola línea con un entero, que representa la longitud máxima de un camino simple con a lo sumo $k$ colores malos.

Ejemplos

Entrada 1

6 1
1 1 1
1 1 4
1 2 2
1 2 8
1 3 100

Salida 1

108

Nota

Elige el camino desde el vértice $5$ hasta el vértice $6$, pasando sucesivamente por los vértices $5, 1, 6$, con longitud $8 + 100 = 108$.

Este camino no pasa por ninguna arista de color $1$ y pasa por todas las aristas de color $3$, por lo que los colores $1, 3$ son buenos. Solo pasa por una de las dos aristas de color $2$, por lo que el color $2$ es malo.

Este camino tiene exactamente un color malo, cumpliendo el requisito. Se puede demostrar que no existe ningún camino válido más largo.

Entrada 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

Salida 2

35

Nota

Elige el camino desde el vértice $8$ hasta el vértice $9$, pasando sucesivamente por los vértices $8, 4, 2, 1, 3, 6, 9$, con longitud $8 + 5 + 3 + 4 + 6 + 9 = 35$.

Este camino pasa por todas las aristas de los colores $1, 2, 5$ y por ninguna arista de los colores $3, 4$, por lo que no tiene colores malos y cumple el requisito. Se puede demostrar que no existe ningún camino válido más largo.

Entrada 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

Salida 3

16

Nota

Elige el camino desde el vértice $7$ hasta el vértice $8$, pasando sucesivamente por los vértices $7, 2, 1, 3, 8$, con longitud $2 + 6 + 5 + 3 = 16$.

Este camino pasa por dos de las tres aristas de color $1$, por lo que el color $1$ es malo. Pasa por todas las aristas de los colores $3, 4$ y por ninguna arista de otros colores, por lo que tiene exactamente un color malo y cumple el requisito.

El camino desde el vértice $7$ hasta el vértice $9$ tiene longitud $17$, pero los colores $1, 2$ son ambos malos, por lo que no cumple el requisito. Se puede demostrar que no existe ningún camino válido de longitud mayor que $16$.

Restricciones

Para todos los datos de prueba, se cumple que:

  • $2 \le n \le 2 \times 10^5$;
  • $k \in \{0, 1\}$;
  • Para cada $i = 2, 3, \ldots, n$, se tiene $1 \le p_i < i$, $1 \le c_i \le n$ y $0 \le w_i \le 10^9$.

Subtareas

Este problema utiliza evaluación por grupos (bundled testing) con dependencias razonables entre subtareas.

Subtarea $n \le$ $k =$ Propiedad especial Puntos
$1$ $200$ $0$ o $1$ Ninguna $5$
$2$ $3000$ $0$ o $1$ Ninguna $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$ Ninguna $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$ Ninguna $11$
$13$ $2 \times 10^5$ $1$ Ninguna $13$
  • Propiedad especial A: Para cada color, todas las aristas de ese color forman un subgrafo conexo.
  • Propiedad especial B: Cada color aparece a lo sumo dos veces.
  • Propiedad especial C: Para cada $i = 2, 3, \ldots, n$, $p_i$ se genera aleatoria e independientemente con igual probabilidad entre los enteros $1, 2, \ldots, i - 1$.
  • Propiedad especial D: Para cada color, existe un camino simple con el vértice $1$ como uno de sus extremos que contiene todas las aristas de ese color.

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.