自动搬运

查看原文

来自洛谷，原作者为

	1jia1 deep dark fantasy

搬运于2025-08-24 22:12:37，当前版本为作者最后更新于2019-08-29 21:18:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意：给定一棵有根树及每个点的权值，多次询问一个点的子树中所有点的权值构成的多重集中，等概率随机选一个子集，这个子集中所有元素的乘积的期望。

由于题目中每个点被打中的概率都是50%，肉眼可见所有子集被选中概率都是相等的。

题目要求的这个东西，如果看不懂，可以理解成在一个序列中的某一段区间中，所有 子序列的元素乘积 之和。

我们先设一个点的子树中的所有点在一个多重集中，为$x_1$,$x_2$,$x_3$,...

将一个集合中所有元素的乘积表示van。

于是，我们可以列出这个多重集的所有子集的van 之和的计算式：

右边的和式的意义是，每个点都有概率被选中。这样，它被选中时对van的贡献就是乘上它本身的数值，没被选中时对van的贡献就是乘1，也就是对答案没有贡献。

左边有一个-1，是因为一个也没打中时的得分是0而不是1，但右边的和式多计算了一个1，所以把它减掉。

具体实现中，只需要一遍dfs，预处理出每个点的size和prod，prod为子树中所有点的权值+1之积。每次询问时，我们便可以O(1)回答。

对于点x，答案就是$\frac{prod[x]-1}{2^{size[x]}}$。

需要注意的是，分母不能简单地用位运算，否则会爆long long。

代码如下：

#include <iostream>
#include <cstdio>
#define N 20000001
#define ha 19260817
#define ll long long
int n,m,num[N], h[N],cnt, size[N],prod[N];
struct edge{
	int next,to;
}e[N<<1];
inline void read(int &out)
{
	out=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while('0'<=c&&c<='9')out=out*10+c-'0',c=getchar();
	return;
}
inline void add(int u,int v)
{
	e[++cnt].next=h[u];
	h[u]=cnt;
	e[cnt].to=v;
	return;
}
inline long long div(ll x)
{
	int k=ha-3;
	long long out=x,xx=x;
	while(k)
	{
		if(k&1)out=(out*xx)%ha;
		xx=(xx*xx)%ha;
		k>>=1;
	}
	return out;
}
inline long long pow(ll x,int k)
{
	long long out=x,xx=x;
	k--;
	while(k)
	{
		if(k&1)out=(out*xx)%ha;
		xx=(xx*xx)%ha;
		k>>=1;
	}
	return out;
}
inline void dfs(int x,int fa)
{
	size[x]=1,prod[x]=num[x];
	for(int i=h[x],v;i;i=e[i].next)
	{
		v=e[i].to;
		if(v==fa)continue;
		dfs(v,x);
		size[x]+=size[v],prod[x]=(int)((ll)prod[x]*(ll)prod[v]%ha);
	}
	return;
}
int main()
{
	read(n),read(m);
	for(int i=1;i<=n;i++)read(num[i]),num[i]=(num[i]+1)%ha;
	for(int i=1,u,v;i<n;i++)
	{
		read(u),read(v);
		add(u,v);add(v,u);
	}
	dfs(1,1);
	ll out=0;
	for(int i=1,x;i<=m;i++)
	{
		read(x);
		out=(out+(ll)(prod[x]-1)*(ll)div(pow(2,size[x])))%ha;
	}
	printf("%d\n",out);
	return 0;
}