[原创]hdu 5416 CRB and Tree [思维]【树】

2017-03-10 00:33:47 Tabris_ 阅读数：239

博客爬取于2020-06-14 22:41:23
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/61023246

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5416
————————————————————————————————
CRB and Tree

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

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个节点的生成树树上,每个边有一个边权
就是定义f(u,v)为树上u->v路径上边权的异或和 ,
有q次查询,每次问你在这棵树上,f()=s的情况有多少种

解题思路:
这其实是一个思维题
通过遍历我们能够知道每一个点到根节点路径上的异或和
因为异或运算满足消去律,所以f(1,u)^f(1,v)=f(u,v);

通过这些我们就好计算了, 只要一遍dfs预处理出每个点到根节点的f(),hash一下 ,
最后计算就行

注意一下 0的情况就行了

附本题代码
—————————————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int    INF = (~(1<<31));
const int    N   = 100000+7;
const double eps = 1e-7;

inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
/****************************************************/

struct edge{
    int to,next,w;
}T[N<<1];
int head[N],tot;
int xt[N],mx;
int cnt[N<<1];

void add(int u,int v,int w){
    T[tot].w=w,T[tot].to=v,T[tot].next=head[u],head[u]=tot++;
    T[tot].w=w,T[tot].to=u,T[tot].next=head[v],head[v]=tot++;
}

void dfs(int u,int fa,int xr){
    xt[u]=xr,cnt[xr]++;
    mx=(mx>xr)?mx:xr;
    for(int i=head[u],to;i!=-1;i=T[i].next){
        to=T[i].to;
        if(to==fa) continue;
        dfs(to,u,xr^T[i].w);
    }
}


int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        mx = tot = 0;
        memset(cnt,0,sizeof(cnt));
        memset(head,-1,sizeof(head));

        int n;
        scanf("%d",&n);
        for(int i=1,u,v,w;i<n;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        dfs(1,-1,0);

        int q,x;
        scanf("%d",&q);
        while(q--){
            scanf("%d",&x);
            LL ans = 0ll;

            for(int i=1;i<=n;i++){
                //if((xt[i]^i)>mx) continue;
                ans+=cnt[x^xt[i]];
            }

            if(!x) ans+=n;
            ans>>=1;
            printf("%I64d\n",ans);
        }
    }
    return 0;
}