CRB and Tree

Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

CRB has a tree, whose vertices are labeled by 1, 2, …, $N$. They are connected by $N$ – 1 edges. Each edge has a weight.
For any two vertices $u$ and $v$(possibly equal), $f(u, v)$ is xor(exclusive-or) sum of weights of all edges on the path from $u$ to $v$.
CRB’s task is for given $s$, to calculate the number of unordered pairs $(u, v)$ such that $f(u, v)\ =\ s$. Can you help him?

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $N$ denoting the number of vertices.
Each of the next $N$ - 1 lines contains three space separated integers $a$, $b$ and $c$ denoting an edge between $a$ and $b$, whose weight is $c$.
The next line contains an integer $Q$ denoting the number of queries.
Each of the next $Q$ lines contains a single integer $s$.
1 ≤ $T$ ≤ 25
1 ≤ $N$ ≤ $10^{5}$
1 ≤ $Q$ ≤ 10
1 ≤ $a$, $b$ ≤ $N$
0 ≤ $c$, $s$ ≤ $10^{5}$
It is guaranteed that given edges form a tree.

Output

For each query, output one line containing the answer.

Sample Input

1 3 1 2 1 2 3 2 3 2 3 4

Sample Output

1 1 0
Hint
For the first query, (2, 3) is the only pair that f(u, v) = 2. For the second query, (1, 3) is the only one. For the third query, there are no pair (u, v) such that f(u, v) = 4.

Hint

wange2014

Source

2015 Multi-University Training Contest 10

提交代码