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 2 1

2 3 2

Sample Output

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

1 2 1

1 3 1

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

#include<bits/stdc++.h>

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<n;i++){

            scanf("%d%d%d",&a,&b,&c);

            addedge(a,b,c);

        }

        dfs(1,-1);

        scanf("%d",&m);

        while(m--){

            INT ans=0;

            scanf("%d",&s);

            for(int i=1;i<=n;++i){

                if(times[val[i]^s]){

                    ans+=times[val[i]^s];

                }

            }

            if(s==0)

                ans+=n;

            printf("%lld\n",ans/2);

        }

    }

    return 0;

}

巴特西

HDU 5416——CRB and Tree——————【DFS搜树】

CRB and Tree

最新文章

热门文章