CRB and Tree

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 967    Accepted Submission(s): 308

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.

 

 

题目大意：给你一棵n个顶点n-1条边的树，每条边有一个权重，定义f(u,v)为结点u到结点v的边权异或值的和，让你求在该树上有多少f(u,v)=s的无序对。

 

解题思路：由于异或的性质。a^a=0。f(u,v)=f(1,u)^f(1,v)。f(u,v)=s  =>  f(1,u)^f(1,v)=s  =>   f(1,v)=f(1,u)^s。那么我们可以枚举u，然后得出f(1,v)为 f(1,u)^s的有多少个。对于s为0的情况，我们发现对于f(1,u)^0的结果还是f(1,u)我们在计算的时候会加一次f(1,u)本身的情况。那么我们最后只需要加上n就可以满足f(u,v)=f(u,u)的情况了。

如样例：

555 

3

1 2 1

1 3 1

1

0

如果不加上n且没除以2之前的结果会是5。如果加上n那么结果就是8。最后除以2以后就是4。

 

#include
        
         using namespace std;const int maxn=1e5+200;int n,tot;struct Edge{    int to,w,next;    Edge(){}    Edge(int too,int ww,int nextt){        to=too;w=ww;next=nextt;    }}edges[maxn*3];typedef long long INT;int head[maxn*2],val[maxn*2];int times[maxn*2];void init(){    tot=0;    memset(head,-1,sizeof(head));    memset(times,0,sizeof(times));    memset(val,0,sizeof(val));}void addedge(int fro , int to,int wei){    edges[tot]=Edge(to,wei,head[fro]);    head[fro]=tot++;    edges[tot]=Edge(fro,wei,head[to]);    head[to]=tot++;}void dfs(int u,int fa){    times[val[u]]++;    for(int i=head[u];i!=-1;i=edges[i].next){        Edge &e=edges[i];        if(e.to==fa)            continue;        val[e.to]=val[u]^e.w;        dfs(e.to,u);    }    return ;}int main(){    //  freopen("1011.in","r",stdin);   // freopen("why.txt","w",stdout);    int t , m, a,b,c ,s;    scanf("%d",&t);    while(t--){        init();        scanf("%d",&n);        for(int i=1;i