题目链接
题解
之前不是有公式吗，当(x,y)互相不影响的情况下，(E(x*y)=E(x)*E(y))。
那么对于一个点，有(frac{1}{2})的概率为(1)或者为他的得分(x)，那么期望就是(frac{1 x}{2})，所以一棵子树的期望就是(frac{得分}{2^{size_{x}}})，当然还有特殊情况就是如果所有都没射中不是(1)，是(0)，那么得分(-1)就行了。
因为有点卡常，所以逆元最好不要后面算，要直接算出(2)的逆元，因为逆元是完全积性函数，所以可以逆元相乘。
#include<cstdio>
#include<cstring>
#define N 2100000
#define M 4100000
using namespace std;
typedef long long LL;
inline void getz(int &x)//快读
{
x=0;register char c=getchar();
while(c<'0' || c>'9')c=getchar();
while(c>='0' && c<='9')x=(x<<3) (x<<1) (c^48),c=getchar();
}
int mod=19260817;
inline int ksc(int x,int y){return ((LL)x*y)%mod;}//乘法
int n,m;
struct node
{
int a,b;
}tr[N];
struct bian
{
int y,next;
}a[M];int len,last[N];
inline void ins(int x,int y){len ;a[len].y=y;a[len].next=last[x];last[x]=len;}
int val[N];
void dfs(int x,int fa)
{
tr[x].b=9630409/*2的逆元*/;tr[x].a=(val[x] 1);
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(y!=fa)
{
dfs(y,x);
tr[x].b=ksc(tr[x].b,tr[y].b);
tr[x].a=ksc(tr[x].a,tr[y].a);
}
}
}
int out;
int main()
{
getz(n);getz(m);
for(register int i=1;i<=n;i ){getz(val[i]);val[i]%=mod;}
for(register int i=1;i<n;i )
{
int x,y;getz(x);getz(y);
ins(x,y);ins(y,x);
}
dfs(1,0);
for(register int i=1;i<=m;i )
{
int x;getz(x);
int x1=tr[x].a-1,x2=tr[x].b;
int ans=ksc(x1,x2);
out=(out ans)%mod;
}
printf("%dn",out);
return 0;
}