Two-Colored Tree#13061

Two-Colored Tree

1 second

256 megabytes

Very hard

You are given a tree with $n$ vertices numbered from $1$ to $n$ . Each edge has a non-negative weight and one of two colors: yellow or blue.

You need to perform the following operation exactly once: choose two distinct vertices $u$ and $v$ and add a new edge between them. The color of the new edge may be chosen arbitrarily, and its weight is $0$ .

It is allowed to add a new edge between vertices that are already connected by an edge of the tree. In this case, the two parallel edges form a cycle of length two, and such a cycle is also considered.

After adding the new edge, exactly one cycle is formed.

We call a cycle good if, when traversing it, the colors of the edges alternate. In other words, any two adjacent edges of the cycle have different colors, including the last and the first edges of the cycle.

The weight of a cycle is the sum of the weights of all its edges.

Find the maximum possible weight of a good cycle that can be obtained after performing the operation.

Input

The first line contains an integer $n$ ( $2 \leq n \leq 2 \cdot 1 0^{5}$ 2 \leq n \leq 2 \cdot 10^5) — the number of vertices in the tree.

Each of the next $n - 1$ n-1 lines contains four values $u$ , $v$ , $w$ , and $c$ ( $1 \leq u, v \leq n$ 1 \leq u, v \leq n, $0 \leq w \leq 1 0^{9}$ 0 \leq w \leq 10^9) — the endpoints of the edge, its weight, and its color, respectively.

If $c =$ Y, the edge is yellow, and if $c =$ B, the edge is blue.

It is guaranteed that the given edges form a tree.

Output

Print one integer — the maximum possible weight of a good cycle.

Examples

Example 1

Example 2

Note

In the first example, you can add an edge between vertices $3$ and $4$ of yellow color.

Then the cycle $3 \to 2 \to 1 \to 4 \to 3$ 3 \to 2 \to 1 \to 4 \to 3 is formed. The colors of its edges in traversal order are blue, yellow, blue, yellow, so the cycle is good.

Its weight is $6 + 4 + 10 = 20$ 6 + 4 + 10 = 20.

In the second example, you can add an edge between vertices $4$ and $8$ of blue color.

Then a cycle is formed that contains the path $4 \to 3 \to 2 \to 1 \to 7 \to 8$ 4 \to 3 \to 2 \to 1 \to 7 \to 8. The colors of the edges on this path are yellow, blue, yellow, blue, yellow. After adding the blue edge between vertices $4$ and $8$ , the colors of all edges in the cycle will alternate.

The weight of this cycle is $7 + 6 + 8 + 9 + 5 = 35$ 7 + 6 + 8 + 9 + 5 = 35.

Scoring

Subtask $1$ ( $20$ points): $n \leq 20$ n \le 20.
Subtask $2$ ( $35$ points): $n \leq 2000$ n \le 2000.
Subtask $3$ ( $30$ points): the tree is a path.
Subtask $4$ ( $20$ points): all edges have the same color.
Subtask $5$ ( $50$ points): if the tree is rooted at vertex $1$ , each vertex has at most two children.
Subtask $6$ ( $70$ points): $n \leq 5 \cdot 1 0^{4}$ n \le 5 \cdot 10^4.
Subtask $7$ ( $175$ points): No additional constraints.