Toska

Time limit: 1.25s Memory limit: 256MB Input: Output:

Eu zic omul sa fie multumit cu saracia sa, caci, daca e vorba, nu bogatia, ci linistea colibei tale te face fericit
— Gluma e ca gen, e moara cu noroc, e gen, o gluma de liceu, nu stiu daca va prindeti.
Ioan Slavici, Mare Clasic

Cerință

Egor, afectat de vremea mohorâtă de iarnă, alege să-și petreacă timpul cu o activitate creativă pentru a-și îmbunătăți starea de spirit — pictura. Astfel, a decis să iasă din casă și să admire natura. Plimbându-se prin Cișmigiu, a observat unul dintre cei mai deosebiți arbori pe care i-a văzut vreodată: un arbore informatic.

Arborele are NN noduri, iar fiecare ramură (muchie) a acestui arbore are o culoare specifică, făcând treaba lui de artist mult mai complicată.

Lui Egor îi place mult simetria, de aceea a decis să accentueze în pictura sa un lanț1^1 în care toate culorile muchiilor din lant apar de un număr par de ori2^2. Totuși, el este adesea indecis; înainte de a alege lanțul pe care îl va accentua, ar dori să știe numărul de lanțuri care ar îndeplini criteriul descris anterior. Ajută-l să afle acest număr!

Date de intrare

Pe prima linie se va afla un singur număr întreg TT — numarul de scenarii diferite.

Fiecare scenariu va fi descris în modul următor:

  • prima linie va contine un număr întreg NN — numărul de noduri din arbore;
  • următoarele N1N-1 linii vor descrie arborele. A ii-a linie va conține câte 3 numere întregi ui,vi,ciu_i, v_i, c_i, reprezentând o muchie de la uiu_i la viv_i de culoare cic_i.

Date de ieșire

Se vor afișa TT linii. A ii-a linie va conține un singur număr întreg, reprezentând răspunsul pentru al ii-lea scenariu.

Restricții și precizări

  • 1^1: Un lanț într-un arbore care unește două noduri xx și yy este o secvență de lungime minimă de muchii care leagă nodul xx de nodul yy.
  • 2^2: Se consideră că o culoare apare de un număr par de ori într-un lanț dacă frecvența acesteia în multimea culorilor muchiilor ce alcătuiesc lanțul este pară;
  • 1T200 0001 \leq T \leq 200\ 000;
  • Suma NN-urilor pentru toate scenariile (notată mai jos cu SNS_N) nu depăseste 200 000200\ 000;
  • 1ciN1 \le c_i \le N;
  • 1ui,viN,uivi1 \leq u_i, v_i \leq N, u_i \neq v_i și nu există i,ji, j astfel încât ui=uju_i = u_j și vi=vjv_i = v_j (sau viceversa);
  • Se garantează că arborele este conex;
  • Este recomandată calcularea răspunsului utilizând tipuri de date pe 6464 de biți.

Subtask-uri

# Punctaj Restricții
0 0 Exemplul
1 9 1SN2001 \leq S_N \leq 200 și ui=i,vi=i+1u_i = i, v_i = i+1 (arborele este un lanț)
2 10 1SN2001 \leq S_N \leq 200
3 13 1SN2 0001 \leq S_N \leq 2\ 000 și și ui=i,vi=i+1u_i = i, v_i = i+1 (arborele este un lanț)
4 14 1SN2 0001 \leq S_N \leq 2\ 000
5 23 1ci501 \leq c_i \leq 50
6 31 Fără restricții suplimentare

Exemplul 1

stdin

2
8
1 5 7
8 1 1
8 6 1
2 7 4
1 4 7
1 2 4
1 3 7
16
2 8 14
1 16 6
3 4 7
15 7 16
6 15 14
1 11 6
15 3 1
8 9 16
3 10 14
11 14 12
8 1 14
9 6 16
9 12 9
5 13 9
3 5 1

stdout

6
8

Log in or sign up to be able to send submissions!