HDU5416 – CRB and Tree(异或性质)

HDU5416

【题意】给出一棵树N(<=10^5)结点，f(u,v)表示u-v路径上所有边值的异或值(u可以等于v,值为0)，Q(<=10)个询问，每个询问x，求出所有f(u,v)点对值为x的数量；

【分析】由于异或性质:同一个数异或两次后等于没有异或；则f(u,v) = f(1,u)^f(1,v)；这样dfs一遍求出所有点到1的异或值；然后每次询问O(n)，由于x^y=s可以转换为x^s = y；而且最大数字只有10^5;任意两个异或值最大为131071;开个数组hash即可；

【AC CODE】530ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = (1e5)+10,MAXIN = 1e4,MAXOUT = 1e4;
char buf[MAXIN], *ps = buf, *pe = buf+1;
inline void rnext(){
	if(++ps == pe) pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
	ans = 0;
	T f = 1;
	if(ps == pe) return false;
	do{ rnext(); if('-' == *ps) f = -1;} while(!isdigit(*ps) && ps != pe);
	if(ps == pe) return false;
	do{ ans = (ans<<1)+(ans<<3)+*ps-48;rnext();}while(isdigit(*ps) && ps != pe);
	ans *= f;
	return true;
}
char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;
inline void write(){ fwrite(bufout,sizeof(char),pout-bufout,stdout);pout = bufout;}
inline void out_char(char c){ *(pout++) = c;if(pout == pend) write();}
inline void out_str(char *s)
{
	while(*s){ *(pout++) = *(s++); if(pout == pend) write(); }
}
template <class T>
inline void out_int(T x) {
	if(!x){ out_char('0');return;}
	if(x < 0) x = -x,out_char('-');
	int len = 0;
	while(x){ outtmp[len++] = x%10+48; x /= 10;}
	outtmp[len] = 0;
	for(int i = 0, j = len-1; i < j; i++,j--) swap(outtmp[i],outtmp[j]);
	out_str(outtmp);
}
int head[MAXN],tol,nxt[MAXN<<1],to[MAXN<<1],cost[MAXN<<1];

inline void add_edge(int u, int v, int c)
{
	nxt[tol] = head[u],to[tol] = v,cost[tol] = c;
	head[u] = tol++;
}
int x[MAXN],cnt[131071+10];
void dfs(int u, int fa)
{
	for(int i = head[u]; ~i; i = nxt[i])
	{
		int v = to[i];
		if(v == fa) continue;
		x[v] = x[u]^cost[i];
		dfs(v,u);
	}
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	in(t);
	while(t--)
	{
		int n;
		in(n);
		clc(head,-1);tol = 0;
		rep(i,1,n)
		{
			int u,v,c;
			in(u);in(v);in(c);
			add_edge(u,v,c);
			add_edge(v,u,c);
		}
		dfs(1,-1);
		int q;
		in(q);
		while(q--)
		{
			int s;
			LL ans = 0;
			in(s);
			clc(cnt,0);
			repe(i,1,n)
			{
				cnt[x[i]]++;
				ans += cnt[x[i]^s];
			}
			out_int(ans),out_char('\n');
		}
	}
	write();
	return 0;
}