Bit üzrə çuxurlar#13103

Bit üzrə çuxurlar

4 saniyə
256 meqabayt

Bir ölkədə şəhər və hər biri iki müxtəlif şəhəri birləşdirən n - 1 ikitərəfli yol var. Yol şəbəkəsi əlaqəlidir: istənilən şəhərdən istənilən başqa şəhərə getmək olar. Deməli, istənilən iki şəhəri dəqiq bir marşrut birləşdirir — heç bir şəhərdən iki dəfə keçməyən yol.

Hər yolda mənfi olmayan tam sayda çuxur var. Prezident iki müxtəlif şəhər arasındakı hər marşrutu hamar etmək istəyir. Marşrut hamar adlanır, əgər onun yollarındakı çuxur saylarının bit üzrə AND-i onların bit üzrə OR-una bərabərdirsə (bit əməlləri aşağıda xatırladılır).

Yol briqadası aşağıdakı əməliyyatı istənilən sayda təkrarlaya bilər:

Tərifləri xatırladaq. Mənfi olmayan tam ədədin nömrəli biti onun 2^i mövqeyindəki ikilik rəqəmidir ( nömrəli bit ən kiçik mərtəbəlidir).

İki müxtəlif şəhər arasındakı hər marşrutu hamar etmək üçün lazım olan minimum əməliyyat sayını tapın.

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 10^5) — test hallarının sayı verilir.

Hər test halının birinci sətrində bir tam ədəd (1 \le n \le 2 \cdot 10^5) — şəhərlərin sayı verilir. Sonrakı n - 1 sətrin hər biri üç tam ədəd , və (1 \le u, v \le n, u \ne v, 0 \le w < 2^{30}) ehtiva edir: və şəhərləri arasında çuxuru olan yol. Yol şəbəkəsinin əlaqəli olduğu təmin edilir.

Bütün test halları üzrə -lərin cəmi 2 \cdot 10^5-i aşmır.

Çıxış

Hər test halı üçün bir tam ədəd — minimum əməliyyat sayını çap edin.

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Birinci test halında şəhərlər 1 - 2 - 3 - 4 - 5 zənciri əmələ gətirir və onun yollarında 1, 0, 0, 1 çuxur var. Bir əməliyyat kifayətdir: nömrəli şəhərdən nömrəli şəhərə gedən marşrutda nömrəli biti əksinə dəyişmək. Onda hər yolda çuxur olar.

İkinci test halında nömrəli şəhərdən nömrəli şəhərə gedən marşrutda i = 2 ilə bir əməliyyat -ni -ya çevirir və hər dörd yolda çuxur olur.

Üçüncü test halında yalnız bir şəhər var, ona görə də müxtəlif şəhərlər arasında marşrut yoxdur və heç nə etmək lazım deyil.

Dördüncü test halında 1 - 2 - 3 - 4 zəncirinin yollarında çuxur var. Üç əməliyyat kifayətdir: i = 0 ilə 1 \to 3 marşrutu, i = 1 ilə 2 \to 3 marşrutu və i = 2 ilə 1 \to 2 marşrutu. Onda hər yolda çuxur olar.

Beşinci test halında nömrəli şəhər , və şəhərləri ilə birləşir, 2 - 3, 4 - 5 və 6 - 7 yolları isə üç budağı davam etdirir. nömrəli şəhərdən çıxan üç yolda çuxur, kənar üç yolda isə çuxur var. İki əməliyyat kifayətdir: i = 0 ilə 2 \to 4 marşrutu və i = 0 ilə 1 \to 6 marşrutu. Onda hər yolda çuxur olar. Göstərmək olar ki, bir əməliyyat kifayət deyil.