2015 多校联赛 ——HDU5416（异或）-白红宇

2015 多校联赛 ——HDU5416（异或）

阅读量：6993 次

发布时间：2019-06-27

本文共 2350 字，大约阅读时间需要 7 分钟。

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

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

b and

c denoting an edge between

a and

b, whose weight is

The next line contains an integer

Q denoting the number of queries.

Each of the next

Q lines contains a single integer

1 ≤

T ≤ 25

1 ≤

N ≤

105

1 ≤

Q ≤ 10

1 ≤

b ≤

0 ≤

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 

题意：

f(u，v) = s(从u->v的异或)中u，v可以有多少对

所以f(u，v) = f(1 , u) ^ f(1 , v)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define N 100050typedef long long ll;int head[N], tot;int num[2*N];int dis[N];struct edge{ int v, w, next;} edg[2*N];void add(int u, int v, int w){ edg[tot].v = v; edg[tot].w = w; edg[tot].next = head[u]; head[u] = tot++;}void dfs(int u, int fa, int val){ dis[u] = val; num[val]++; //记录val的个数 for(int i = head[u]; ~i; i = edg[i].next) { int v = edg[i].v; if(v == fa) continue; dfs(v, u, val^edg[i].w); }}int main(){ int T,u,v,w,m,n; scanf("%d",&T); while(T--) { scanf("%d",&n); tot = 0; memset(head,-1,sizeof(head)); memset(num,0,sizeof(num)); for(int i = 1; i < n; i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs(1,-1,0); scanf("%d", &m); int s; for(int i = 0; i < m; i++) { scanf("%d", &s); int temp; ll ans = 0; for(int i = 1;i <= n;i++) { temp = s^dis[i]; if(temp == dis[i]) //除去本身的那个 ans += num[temp]- 1; else ans += num[temp]; } ans/=2; if(s == 0) //加上自己与自己异或的情况 ans += n; printf("%I64d\n",ans); } } return 0;}