İki Rəngli Ağac#13061

İki Rəngli Ağac

1 saniyə

256 meqabayt

Çox çətin

Sizə $1$ -dən $n$ -ə qədər nömrələnmiş $n$ təpədən ibarət bir ağac verilir. Hər kənarın mənfi olmayan çəkisi və iki rəngdən biri var: sarı və ya mavi.

Aşağıdakı əməliyyatı dəqiq bir dəfə yerinə yetirmək lazımdır: iki müxtəlif təpə $u$ və $v$ seçin və onların arasında yeni bir kənar əlavə edin. Yeni kənarın rəngi istənilən ola bilər, çəkisi isə $0$ -dır.

Ağacda artıq kənarla birləşmiş təpələr arasında da yeni kənar əlavə etməyə icazə verilir. Bu halda, iki paralel kənar uzunluğu iki olan bir dövrə əmələ gətirir və belə dövrə də nəzərə alınır.

Yeni kənar əlavə edildikdən sonra dəqiq bir dövrə yaranır.

Bir dövrəni yaxşı adlandırırıq, əgər onu dolaşarkən kənarların rəngləri növbələşirsə. Başqa sözlə, dövrədə yanaşı olan istənilən iki kənarın rəngi fərqli olmalıdır, o cümlədən son və birinci kənarlar da.

Bir dövrənin çəkisi onun bütün kənarlarının çəkilərinin cəmidir.

Əməliyyatı yerinə yetirdikdən sonra əldə edilə bilən ən böyük çəkili yaxşı dövrənin çəkisini tapın.

Giriş

Birinci sətirdə bir tam ədəd $n$ ( $2 \leq n \leq 2 \cdot 1 0^{5}$ 2 \leq n \leq 2 \cdot 10^5) — ağacdakı təpələrin sayı verilir.

Növbəti $n - 1$ n-1 sətirin hər birində dörd qiymət $u$ , $v$ , $w$ və $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) — kənarın ucları, çəkisi və rəngi verilir.

Əgər $c =$ Y olarsa, kənar sarıdır, əgər $c =$ B olarsa, kənar mavidir.

Verilən kənarların ağac əmələ gətirdiyi zəmanət verilir.

Çıxış

Bir tam ədəd çap edin — mümkün olan ən böyük yaxşı dövrənin çəkisi.

Nümunələr

Nümunə 1

Nümunə 2

Qeyd

Birinci nümunədə, $3$ və $4$ təpələri arasında sarı rəngli bir kənar əlavə edə bilərsiniz.

Onda $3 \to 2 \to 1 \to 4 \to 3$ 3 \to 2 \to 1 \to 4 \to 3 dövrəsi yaranır. Onun kənarlarının dolaşma ardıcıllığında rəngləri mavi, sarı, mavi, sarıdır, buna görə də dövrə yaxşıdır.

Onun çəkisi $6 + 4 + 10 = 20$ 6 + 4 + 10 = 20-dir.

İkinci nümunədə, $4$ və $8$ təpələri arasında mavi rəngli bir kənar əlavə edə bilərsiniz.

Onda $4 \to 3 \to 2 \to 1 \to 7 \to 8$ 4 \to 3 \to 2 \to 1 \to 7 \to 8 yolunu ehtiva edən bir dövrə yaranır. Bu yol üzərindəki kənarların rəngləri sarı, mavi, sarı, mavi, sarıdır. $4$ və $8$ təpələri arasında mavi kənar əlavə edildikdən sonra, dövrədəki bütün kənarların rəngləri növbələşəcək.

Bu dövrənin çəkisi $7 + 6 + 8 + 9 + 5 = 35$ 7 + 6 + 8 + 9 + 5 = 35-dir.

Bal hesablama

Alt tapşırıq $1$ ( $20$ xal): $n \leq 20$ n \le 20.
Alt tapşırıq $2$ ( $35$ xal): $n \leq 2000$ n \le 2000.
Alt tapşırıq $3$ ( $30$ xal): ağac bir yoldur.
Alt tapşırıq $4$ ( $20$ xal): bütün kənarlar eyni rəngdədir.
Alt tapşırıq $5$ ( $50$ xal): ağac $1$ təpəsi kök kimi götürüldükdə, hər təpənin ən çox iki övladı var.
Alt tapşırıq $6$ ( $70$ xal): $n \leq 5 \cdot 1 0^{4}$ n \le 5 \cdot 10^4.
Alt tapşırıq $7$ ( $175$ xal): Əlavə məhdudiyyət yoxdur.