İki Renkli Ağaç#13061

İki Renkli Ağaç

1 saniye

256 megabayt

Çok zor

Size $1$ 'den $n$ 'ye kadar numaralandırılmış $n$ düğümden oluşan bir ağaç veriliyor. Her kenarın negatif olmayan bir ağırlığı ve iki renkten biri vardır: sarı veya mavi.

Aşağıdaki işlemi tam olarak bir kez gerçekleştirmeniz gerekiyor: birbirinden farklı iki düğüm $u$ ve $v$ seçin ve aralarına yeni bir kenar ekleyin. Yeni kenarın rengi keyfi olarak seçilebilir ve ağırlığı $0$ 'dır.

Ağaçta zaten bir kenarla bağlı olan düğümler arasına da yeni bir kenar eklemeye izin verilir. Bu durumda iki paralel kenar uzunluğu iki olan bir çevrim oluşturur ve böyle bir çevrim de dikkate alınır.

Yeni kenar eklendikten sonra tam olarak bir çevrim oluşur.

Bir çevrimi, üzerinde dolaşıldığında kenarların renkleri dönüşümlü olarak değişiyorsa iyi olarak adlandırırız. Başka bir deyişle, çevrimin komşu olan herhangi iki kenarı farklı renkte olmalıdır; buna çevrimin son ve ilk kenarları da dahildir.

Bir çevrimin ağırlığı, tüm kenarlarının ağırlıklarının toplamıdır.

İşlem gerçekleştirildikten sonra elde edilebilecek iyi bir çevrimin mümkün olan en büyük ağırlığını bulun.

Giriş

İlk satırda bir tam sayı $n$ ( $2 \leq n \leq 2 \cdot 1 0^{5}$ 2 \leq n \leq 2 \cdot 10^5) — ağaçtaki düğümlerin sayısı verilir.

Sonraki $n - 1$ n-1 satırın her birinde dört değer $u$ , $v$ , $w$ ve $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) — sırasıyla kenarın uçları, ağırlığı ve rengi verilir.

Eğer $c =$ Y ise kenar sarıdır, eğer $c =$ B ise kenar mavidir.

Verilen kenarların bir ağaç oluşturduğu garanti edilir.

Çıktı

Bir tam sayı yazdırın — iyi bir çevrimin mümkün olan en büyük ağırlığı.

Örnekler

Örnek 1

Örnek 2

Not

Birinci örnekte, $3$ ve $4$ düğümleri arasına sarı renkli bir kenar ekleyebilirsiniz.

Bu durumda $3 \to 2 \to 1 \to 4 \to 3$ 3 \to 2 \to 1 \to 4 \to 3 çevrimi oluşur. Dolaşma sırasına göre kenarlarının renkleri mavi, sarı, mavi, sarıdır, dolayısıyla çevrim iyidir.

Ağırlığı $6 + 4 + 10 = 20$ 6 + 4 + 10 = 20'dir.

İkinci örnekte, $4$ ve $8$ düğümleri arasına mavi renkli bir kenar ekleyebilirsiniz.

Bu durumda $4 \to 3 \to 2 \to 1 \to 7 \to 8$ 4 \to 3 \to 2 \to 1 \to 7 \to 8 yolunu içeren bir çevrim oluşur. Bu yol üzerindeki kenarların renkleri sarı, mavi, sarı, mavi, sarıdır. $4$ ve $8$ düğümleri arasına mavi kenar eklendikten sonra, çevrimdeki tüm kenarların renkleri dönüşümlü olacaktır.

Bu çevrimin ağırlığı $7 + 6 + 8 + 9 + 5 = 35$ 7 + 6 + 8 + 9 + 5 = 35'tir.

Puanlama

Alt görev $1$ ( $20$ puan): $n \leq 20$ n \le 20.
Alt görev $2$ ( $35$ puan): $n \leq 2000$ n \le 2000.
Alt görev $3$ ( $30$ puan): ağaç bir yoldur.
Alt görev $4$ ( $20$ puan): tüm kenarlar aynı renktedir.
Alt görev $5$ ( $50$ puan): ağaç $1$ düğümünden köklendiğinde, her düğümün en fazla iki çocuğu vardır.
Alt görev $6$ ( $70$ puan): $n \leq 5 \cdot 1 0^{4}$ n \le 5 \cdot 10^4.
Alt görev $7$ ( $175$ puan): Ek kısıt yoktur.