Freaky Tree
/
No tags
Problem
Editorial
Analytics

Acfreak was working on a tree problem which he finds hard to solve. So he called upon you to help him out to solve the task. You are given an undirected weighted tree rooted at 1. You need to count the number of distinct paths from the root to leaves such that the XOR-Value of the weights in the path is odd

Input

Assume that Acfreak was working on $T$ different trees. For each tree, you will be given an integer $N$ that denotes the total number of nodes. The next $N-1$ lines contain three integers $a_i,b_i,c_i$ which denote that there is an edge between the nodes $a_i$ and $b_i$ with weight $c_i$.

Output

In a separate line, print the count of distinct paths satisfying the requirement.

Constraints
$1 \le T \le 10 \\ 1 \le N \le 10^5 \\ 1 \le a_i, b_i \le N\\ w_i \in {0,1}$

SAMPLE INPUT
1
7
1 2 0
1 3 1
2 4 0
2 5 1
3 6 1
3 7 0
SAMPLE OUTPUT
2
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...