Problem 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 ≤ 105
1 ≤ Q ≤ 10
1 ≤ a, b ≤ N
0 ≤ c, s ≤ 105
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.

题意：给你一棵树，然后Q个问题，每个问题询问有存在多少个f(u,v)等于s其中u<=v，f(u,v)表示节点u到节点v所有边的权值异或和。

解法：位运算的巧妙应用。f(u,v)=f(1,u)^f(1,v)，因为假设u,v的lca是p,那么1~p这些节点都是公用的，这部分被异或了两次，就抵消了。然后对于Q次问题，假设某一次问题是s，则有s=f(u,v)=f(1,u)^f(1,v)。那么有f(1,v)=s^f(1,u)，也就是说，如果我们DFS到节点u，算出了f(1,v)，那么对于某一个s，我们就需要算出f(1,v)等于多少，然后再通过cnt数组知道f(1,v)有多少个，把这个值累加到s这个查询的答案中去，就这样DFS遍历完整个树，答案就离线处理完了。复杂度O(Q*N)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
struct edge{
    int to,w,next;
}E[maxn*2];
int head[maxn], edgecnt;
void init(){
    edgecnt=0;
    memset(head,-1,sizeof(head));
}
void add(int u, int v, int w){
    E[edgecnt].to = v, E[edgecnt].next = head[u], E[edgecnt].w = w, head[u] = edgecnt++;
}
LL ans[maxn];
int n, m;
int q[maxn], cnt[maxn*4];
void dfs(int u, int fa, int s){
    cnt[s]++;
    for(int j=1; j<=m; j++){
        ans[j] += 1LL*cnt[s^q[j]];
    }
    for(int i=head[u]; ~i; i=E[i].next){
        int v = E[i].to;
        if(v!=fa){
            dfs(v,u,s^E[i].w);
        }
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        init();
        for(int i=1; i<n; i++){
            int u, v, w;
            scanf("%d %d %d", &u,&v,&w);
            add(u, v, w);
            add(v, u, w);
        }
        memset(cnt, 0, sizeof(cnt));
        memset(ans, 0, sizeof(ans));
        scanf("%d", &m);
        for(int i=1; i<=m; i++){
            scanf("%d", &q[i]);
        }
        dfs(1,-1,0);
        for(int i=1; i<=m; i++) printf("%lld\n", ans[i]);
    }
    return 0;
}