HDU ACM 5416 CRB and Tree DFS+前缀跟

HDU ACM 5416 CRB and Tree DFS+前缀和
题意：在一棵树上有n个点，n-1条边，每条边都有一个权值。 
令f(u,v)等于u到v这条路径上的异或和。 
现在给你Q次询问(Q<=10) 

询问f(u,v)=s的路径有多少条。

分析：Q比较小，可直接用O(n)复杂度来做。 
先用sum[u]保存下，从根节点到u的异或和是多少。 
用一个hash map来保存，sum[u]出现了多少次。 
每次就查询hash map中s ^ sum[u]出现了多少次。 
查询的总和除以2就是最终结果。
X^Y=S;X^S=Y;X^Y^X=Y。

注意：
如果s=0时，f(u,u)也满足条件，所以还要再加上n。结果会超32位int。

#include<iostream>
#include<vector>
using namespace std;

#define maxn ((int)2e5+10)

struct edge
{
	edge(){}
	edge(int _u,int _v,int _val):u(_u),v(_v),val(_val){}
	int u,v,val;
};
int sum[maxn],MAP[maxn];   //异或和及hash MAP
vector<edge> G[maxn];      //树
int n,q;

void init()
{
	int i;

	memset(MAP,0,sizeof(MAP));
	for(i=1;i<=n;i++)
		G[i].clear();
}

void add_edge(int u,int v,int val)
{
	G[u].push_back(edge(u,v,val));
}

void dfs(int u,int pre,int val)
{
	int i,v;

	sum[u]=val;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i].v;
		if(v==pre) continue;
		dfs(v,u,val^G[u][i].val);
	}
}

__int64 cal(int s)
{
	__int64 ans=0,i;

	for(i=1;i<=n;i++)
		ans+=MAP[s^sum[i]];

	if(s==0) ans+=n;
	return ans/2;
}

int main()
{
	int T;
	int u,v,val,s,i;

	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		init();
		for(i=1;i<n;i++)
		{
			scanf("%d%d%d",&u,&v,&val);
			add_edge(u,v,val);
			add_edge(v,u,val);
		}
		dfs(1,-1,0);
		for(i=1;i<=n;i++)
			MAP[sum[i]]++;
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d",&s);
			printf("%I64d\n",cal(s));
		}
	}
    return 0;
}