Двокольорове дерево#13061

Двокольорове дерево

1 секунда

256 мегабайтів

Дуже складна

Дано дерево з $n$ вершин, пронумерованих від $1$ до $n$ . Кожне його ребро має невід'ємну вагу та один із двох кольорів: жовтий або блакитний.

Потрібно рівно один раз виконати таку операцію: вибрати дві різні вершини $u$ та $v$ і провести між ними нове ребро. Колір нового ребра можна вибрати довільно, а його вага дорівнює $0$ .

Дозволяється провести нове ребро між вершинами, між якими вже існує ребро дерева. У такому випадку два паралельні ребра утворюють цикл із двох ребер, і такий цикл також розглядається.

Після додавання нового ребра утворюється рівно один цикл.

Назвемо цикл хорошим, якщо під час його обходу кольори ребер чергуються. Іншими словами, будь-які два сусідні ребра циклу мають різні кольори, зокрема останнє та перше ребра циклу.

Вагою циклу називається сума ваг усіх його ребер.

Знайдіть максимальну можливу вагу хорошого циклу, який можна отримати після виконання операції.

Вхідні дані

У першому рядку задано ціле число $n$ ( $2 \leq n \leq 2 \cdot 1 0^{5}$ 2 \leq n \leq 2 \cdot 10^5 ) — кількість вершин дерева.

У кожному з наступних $n - 1$ n-1 рядків задано чотири значення $u$ , $v$ , $w$ та $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) — кінці ребра, його вагу та колір відповідно.

Якщо $c =$ Y, ребро жовте, а якщо $c =$ B, ребро блакитне.

Гарантується, що задані ребра утворюють дерево.

Вихідні дані

Виведіть одне ціле число — максимальну можливу вагу хорошого циклу.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі можна додати ребро між вершинами $3$ і $4$ жовтого кольору.

Тоді утвориться цикл $3 \to 2 \to 1 \to 4 \to 3$ 3 \to 2 \to 1 \to 4 \to 3. Кольори його ребер у порядку обходу: блакитний, жовтий, блакитний, жовтий, тому цикл є хорошим.

Його вага дорівнює $6 + 4 + 10 = 20$ 6 + 4 + 10 = 20.

У другому прикладі можна додати ребро між вершинами $4$ і $8$ блакитного кольору.

Тоді утвориться цикл, що містить шлях $4 \to 3 \to 2 \to 1 \to 7 \to 8$ 4 \to 3 \to 2 \to 1 \to 7 \to 8. Кольори ребер цього шляху: жовтий, блакитний, жовтий, блакитний, жовтий. Після додавання блакитного ребра між вершинами $4$ і $8$ кольори всіх ребер циклу чергуватимуться.

Вага цього циклу дорівнює $7 + 6 + 8 + 9 + 5 = 35$ 7 + 6 + 8 + 9 + 5 = 35.

Оцінювання

Підзадача $1$ ( $20$ балів): $n \leq 20$ n \le 20.
Підзадача $2$ ( $35$ балів): $n \leq 2000$ n \le 2000.
Підзадача $3$ ( $30$ балів): дерево є шляхом.
Підзадача $4$ ( $20$ балів): усі ребра мають однаковий колір.
Підзадача $5$ ( $50$ балів): якщо вкорінити дерево у вершині $1$ , кожна вершина матиме не більше двох дітей.
Підзадача $6$ ( $70$ балів): $n \leq 5 \cdot 1 0^{4}$ n \le 5 \cdot 10^4.
Підзадача $7$ ( $175$ балів): Без додаткових обмежень.