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

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

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?

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?

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.

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.

提交代码