CRB and Tree

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

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.

Author

KUT（DPRK）

Source

2015 Multi-University Training Contest 10

题意：给你一棵树，路径上有权值，q个询问每次给你一个A，要你找出所有路径权值异或和为A的方案数

题解：定义一个根节点1，dfs出所有节点与根节点的异或和，   根据异或：a^b=c,那么b^c=a

///
#include
#include
#include
#include
#include
#include
#include
#include

        for(int j=;j<=maxn;j++)  
        {if(!hashs\[j\])continue;  
                if((a^j)==j)ans+=(hashs\[j\]\*(hashs\[j\]-));  
                else {  
                    ans+=(hashs\[j\]\*hashs\[a^j\]);  
                }  
                //if(ans!=0)cout<<j<<" "<<ans<<endl;  
        }ans=ans/;  
        if(a==)ans+=n;  
        cout<<ans<<endl;  
    }

}  
return ;  

}

代码

   特别考虑A==0的情况，最后方案数/2