前言

很基础的一道树形DP题。

题目

AtCoder

题目大意：

给定一棵 \(N\) 个点的带权树，询问每个无序点对间的异或距离和。答案对 \(10^9+7\) 取模。

\(2\le N\le 2\times 10^5;0\le w_i\le 2^{60}.\)

讲解

先考虑边权是 \(0,1\) 怎么做。

显然可以直接DP，令 \(dp[i][j]\) 表示从下往上到 \(i\) 异或距离为 \(j\) 的路径数。转移很显然：

\[dp[u][i]=\underset{v\in son_x}{\sum}dp[v][i\oplus w_{u,v}]+(i\oplus w_{u,v}\oplus 1) \]

中途顺便统计答案即可。

由于每个二进制位之间不会互相影响，所以我们对于每一位单独做即可。

时间复杂度：\(O(n\log_2\max\{w_i\})\)。

当然你也可以从上往下做，用经典结论 \(dis_{1,u}\oplus dis_{1,v}=dis{u,v}\) 计数。

其实本质是相同的。

注意long long 的使用以及溢出问题。

代码

从下往上。

int head[MAXN],tot;
struct edge
{
	int v,nxt;
	LL w;
}e[MAXN << 1];
void Add(LL x){ans = (ans + x) % MOD;}
void Add_Edge(int x,int y,LL z)
{
	e[++tot].v = y;
	e[tot].w = z;
	e[tot].nxt = head[x];
	head[x] = tot;
}
void Add_Double_Edge(int x,int y,LL z)
{
	Add_Edge(x,y,z);
	Add_Edge(y,x,z);
}
 
LL dp[MAXN][2];
void dfs(int x,int fa,int o)
{
	dp[x][0] = dp[x][1] = 0;
	for(int i = head[x]; i ;i = e[i].nxt)
	{
		int v = e[i].v,w = (e[i].w >> o) & 1;
		if(v == fa) continue;
		dfs(v,x,o);
		if(!w)
		{
			Add(dp[x][0] * dp[v][1] % MOD * ((1ll << o) % MOD));
			Add(dp[x][1] * (dp[v][0]+1) % MOD * ((1ll << o) % MOD));
			dp[x][0] += dp[v][0]+1;
			dp[x][1] += dp[v][1];
		}
		else 
		{
			Add(dp[x][0] * (dp[v][0]+1) % MOD * ((1ll << o) % MOD));
			Add(dp[x][1] * dp[v][1] % MOD * ((1ll << o) % MOD));
			dp[x][0] += dp[v][1];
			dp[x][1] += dp[v][0]+1;
		}
	}
	Add(dp[x][1] * ((1ll << o) % MOD));
}
 
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n = Read();
	for(int i = 1;i < n;++ i)
	{
		int u = Read(),v = Read();
		Add_Double_Edge(u,v,Read());
	}
	for(int i = 0;i <= 60;++ i) dfs(1,0,i);
	Put(ans);
	return 0;
}