Árbol de Dos Colores#13061
Se le da un árbol con vértices numerados de a . Cada arista tiene un peso no negativo y uno de dos colores: amarillo o azul.
Hay que realizar exactamente una vez la siguiente operación: elegir dos vértices distintos y y añadir una nueva arista entre ellos. El color de la nueva arista puede ser cualquiera, y su peso es .
Está permitido añadir una nueva arista incluso entre vértices que ya están conectados por una arista. En ese caso, dos aristas paralelas forman un ciclo de longitud dos, y dicho ciclo también se considera.
Después de añadir la nueva arista, se forma exactamente un ciclo.
Llamamos a un ciclo bueno si, al recorrerlo, los colores de las aristas alternan. En otras palabras, cualesquiera dos aristas adyacentes del ciclo deben tener colores distintos, incluyendo también la última y la primera arista.
El peso de un ciclo es la suma de los pesos de todas sus aristas.
Después de realizar la operación, encuentre el peso máximo posible de un ciclo bueno que se pueda obtener.
La primera línea contiene un entero (2 \leq n \leq 2 \cdot 10^5) — el número de vértices del árbol.
Cada una de las siguientes n-1 líneas contiene cuatro valores , , y (1 \leq u, v \leq n, 0 \leq w \leq 10^9) — los extremos de una arista, su peso y su color.
Si Y, la arista es amarilla; si B, la arista es azul.
Se garantiza que las aristas dadas forman un árbol.
Imprima un entero — el mayor peso posible de un ciclo bueno.
Ejemplo 1
Ejemplo 2
En el primer ejemplo, puede añadir una arista amarilla entre los vértices y .
Entonces se forma el ciclo 3 \to 2 \to 1 \to 4 \to 3. En el orden de recorrido, los colores de sus aristas son azul, amarillo, azul, amarillo, por lo que el ciclo es bueno.
Su peso es 6 + 4 + 10 = 20.
En el segundo ejemplo, puede añadir una arista azul entre los vértices y .
Entonces se forma un ciclo que contiene el camino 4 \to 3 \to 2 \to 1 \to 7 \to 8. Los colores de las aristas en este camino son amarillo, azul, amarillo, azul, amarillo. Después de añadir la arista azul entre los vértices y , todos los colores de las aristas del ciclo alternarán.
El peso de este ciclo es 7 + 6 + 8 + 9 + 5 = 35.
Subtarea ( puntos): n \leq 20.
Subtarea ( puntos): n \leq 2000.
Subtarea ( puntos): el árbol es un camino.
Subtarea ( puntos): todas las aristas tienen el mismo color.
Subtarea ( puntos): al considerar el vértice como raíz, cada vértice tiene como máximo dos hijos.
Subtarea ( puntos): n \leq 5 \cdot 10^4.
Subtarea ( puntos): sin restricciones adicionales.