ICPC Xi'an invitation 2019--J.And And And

题意：

给出一棵根为 (1) 的树，和树上所有边的边权，求
.

(sum^{n}_{u=1} sum^{n}_{v=1} sum^{}_{u^{prime }in E(u,v)} sum^{}_{v^{prime }in E(u,v)} [u<v][u^{prime }<v^{prime }][X(u^{prime },v^{prime }_{})=0])
其中 (E(u,v)) 表示树上简单路径 (u ightarrow v) 上的所有点构成的点集， (X(u,v)) 表示树上简单路径 (u ightarrow v) 的异或和。

思路：

• 转化一下这个公式，此题就是求树上所有简单路径中的异或和为 (0) 的子路径的数量。
• 考虑求树上异或和为 (0) 的路径对答案的贡献。
• 1、路径两端 ((u,v)) 在不同链上，那么贡献很显然就是 (siz[u] imes siz[v])
• 2、路径两端 ((u,v)) 在同一条链上，设 (depth[v]>depth[u])，那么贡献就是 ((n-siz[u]) imes siz[v])。
• 对于一条路径的异或和为 (0) ，相当于路径两端的两个点到一个相同的点的异或和相等。显然可以预处理出每个点到根的异或和。
• 显然可以用 (dfs) 实现，用一个 (map) 记录异或和，那么在考虑答案贡献是只要看异或和相同的两个点的贡献即可。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500005;
const ll mod=1e9+7;

typedef pair<ll,ll> P;
ll siz[maxn],Xor[maxn];
ll n;
vector<P>g[maxn];
ll ans=0;
map<ll,ll>mp;

void dfs(int u)
{
	siz[u]=1;
	for(auto to:g[u]){
		Xor[to.first]=(Xor[u]^to.second);
		dfs(to.first);
		siz[u]+=siz[to.first];
	}
}
void dfs2(int u)
{
	ll temp=Xor[u];
	//cout<<siz[u]<<" "<<mp[temp]<<endl;
	ans=(ans+siz[u]*mp[temp])%mod;	
	for(auto to:g[u]){
		mp[temp]+=(n-siz[to.first]);
		dfs2(to.first);
		mp[temp]-=(n-siz[to.first]);
	}
	mp[temp]+=siz[u];
}	

int main()
{
	scanf("%lld",&n);
	for(int i=2;i<=n;i++){
		ll fa,w;
		scanf("%lld%lld",&fa,&w);
		g[fa].push_back(P(i,w));
	}
	dfs(1);
	dfs2(1);
	printf("%lld
",ans);
}