自动搬运

查看原文

来自洛谷，原作者为

	LKY928261 **

搬运于2025-08-24 22:44:13，当前版本为作者最后更新于2023-01-27 13:52:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

验题人题解

考虑一个集合中一个点能产生贡献的情况。此时该点被集合包含，集合内的所有点在同一条树链上，且该集合中有至少两个点。

显然，一个点 $u$ 在一条长度为 $l$ 的链上产生的贡献为 $2^{l-1}-1$（除去 $u$ 每个点选或不选，再去掉只剩 $u$ 一个点的情况）。

由此延伸到一个点 $u$ 的总贡献：假定整棵树以 $u$ 为根，对每棵子树统计出从子树根出发的方案数（不包含全不选）。对于单棵子树，设其方案数为 $x$，则贡献为 $x$；对于不同的两棵子树，设其方案数分别为 $x,y$，则贡献为 $xy$。只不过此时单个子树的方案数并非简单的 2 的次幂，而是由它下方的子树合并而来。

考虑原题。对于结点 $u$，在以 $u$ 为根的子树中按上述方法统计一遍，再将子树内与子树外的进行一次合并统计。由于方法多样，且参考代码中有较详细的注释，具体实现方式此处不细讲。

时间复杂度 $O(n)$，优于 std。

参考代码

非唯一解法，仅供参考。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define _ 1000005
#define Mod 1000000007
void pls(ll &x,ll y){x=(x+y)%Mod;}
ll n,x,y,a[_],ans,s[_],cnt,hd[_];
//a[u]: 在以u为根的子树内，u必选，其余点可以全不选，
//且所有集合内的点都在同一条以u为一端的链上的方案数
struct o{ll nxt,to;}edg[_];
void add(ll x,ll y){edg[++cnt].nxt=hd[x];hd[x]=cnt;edg[cnt].to=y;}
//这里由于代码习惯，所有的u都写成了x，请见谅
void dfs1(ll x,ll fa){
	a[x]=1;
	for(ll i=hd[x];i;i=edg[i].nxt)if(edg[i].to!=fa){
		dfs1(edg[i].to,x);
		pls(s[x],(a[x]-1)*(a[edg[i].to]*2-1));//统计当前子树内部产生的贡献
		pls(a[x],a[edg[i].to]*2-1);//更新当前子树下的方案数
	}
}
void dfs2(ll x,ll fa,ll z){//z: 该子树外的方案数（限制同a[u]）
	pls(s[x],a[x]*z-1);//直接统计穿过子树内外的链产生的贡献
	for(ll y,i=hd[x];i;i=edg[i].nxt)if(edg[i].to!=fa){
		y=edg[i].to;
		dfs2(y,x,((a[x]-a[y]*2+1+Mod*2)%Mod+z-1)*2%Mod);//更新
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(ll i=1;i<n;i++)cin>>x>>y,add(x,y),add(y,x);
	dfs1(1,0);dfs2(1,0,1);
	for(ll i=1;i<=n;i++)ans^=s[i]*i;
	cout<<ans<<'\n';
}