HDU 5416 CRB and Tree（dfs 异或逆运算） CRB and Tree

53 阅读 0 评论 35 点赞

我是靠谱客的博主专一冷风，最近开发中收集的这篇文章主要介绍HDU 5416 CRB and Tree（dfs 异或逆运算） CRB and Tree，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

CRB and Tree

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 760 Accepted Submission(s): 248

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

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.

贴个代码记住 ^ 的优先级小于 < 。。。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;

const int Maxxor = (1 << 17) + 10;
struct Edge{int to, cost;}e;
vector<Edge> g[100010];
bool vis[100010], viss[Maxxor];
long long cnt[Maxxor];
void dfs(int u, int Xor)
{
    vis[u] = true;
    for(int i = 0; i < g[u].size(); i++)
    {
        e = g[u][i];
        if(!vis[e.to])
        {
            cnt[e.cost ^ Xor]++;
            dfs(e.to, e.cost ^ Xor);
        }
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        for(int i = 0; i < 100010; i++)
        {
            g[i].clear();
        }
        scanf("%d", &n);
        for(int i = 1; i < n; i++)
        {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            e.to = v, e.cost = c;
            g[u].push_back(e);
            e.to = u;
            g[v].push_back(e);
        }
        memset(vis, 0, sizeof(vis));
        memset(cnt, 0, sizeof(cnt));
        dfs(1, 0);
        int Q;
        scanf("%d", &Q);
        while(Q--)
        {
            int s;
            scanf("%d", &s);
            long long ans = 0;
            memset(viss, 0, sizeof(viss));
            ans += cnt[s];
            if(s == 0)
            {
                ans += n;
                for(int i = 0; i < Maxxor; i++)
                {
                    if(cnt[i])
                    {
                        ans += (cnt[i] * (cnt[i] - 1)) / 2;
                    }
                }
            }
            else
            {
                for(int i = 0; i < Maxxor; i++)
                {
                    if((s ^ i) < Maxxor && !viss[i] && !viss[s ^ i])
                    {
                        ans += cnt[i] * cnt[s ^ i];
                        viss[i] = viss[s ^ i] = true;
                    }
                }
            }
            printf("%I64dn", ans);
        }
    }
    return 0;
}