链接：https://www.luogu.com.cn/problem/P8334
题解：最小值期望显然可以转化为\(>=x\)的概率求和，所以我们可以考虑一个暴力，每次将\(>=x\)的点加入称为黑点，然后进行\(dp\)。那么对于那一些全黑的子树，\(dp\)值可以轻松确定，对于有白的子树，进入了就不能出来了，就只会进入一次。
考虑整体\(dp\)，用线段树合并，那么一个子树全黑当且仅当\(minn_{x}>=d\)，那么如果我们将\(x\)的所有子节点排序，全黑的就是一段后缀，本质不同的后缀数仅有\(son\)个。这样对于一个后缀，其贡献的答案的区间实际上是\((minn_{p_{x}},minn_{p_{x+1}}]\)的形式。
实际上，对于\((minn_{p_{x}},minn_{p_{x+1}}]\)这段区间，我们只关心其有白儿子节点的儿子概率和，因为进入每一个儿子是等概率的，这样我们在保留线段树时仅需保留\((minn_{p_{x}},inf]\)这段区间上的\(dp\)值，而且因为\([0,minn_{p_{x}}]\)这段区间的值一定为\(sz_{x}\)，故这样线段树合并是方便的。
那么我们还要面临的一个问题是如何统计概率的转移系数，注意到一个点会在一个黑儿子结束(\(A\))，或会不断在黑跳然后到一个有白儿子(\(B\))，下面我们令黑儿子个数为\(cnt_{black}\)，\(sz\)和为\(sz_{black}\)，有白儿子个数为\(cnt_{white}\)，\(sz\)和为\(sz_{white}\)。
\(A\)的贡献即为\(1/(1+cnt_{white})\times sz_{black}\)，即在排列中一个黑儿子在所有有白儿子前的概率乘个数，\(B\)的贡献则为\(1/cnt_{white}\times res\)，\(res\)为线段树合并求的和。
那么我们只需要维护一个支持区间\(ax+b->x\)的线段树，维护两个\(lazy\)标记即可。
复杂度\(O(n log n)\)。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 400000
#define mod 998244353
#define inf 1e9
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int fast_pow(int a,int b)
{
int res=1,mul=a;
while (b)
{
if (b&1) res=1ll*res*mul%mod;
mul=1ll*mul*mul%mod,b>>=1;
}
return res;
}
bool used[N+1];
int n,rt,rts[N+1],a[N+1],minn[N+1],fac[N+1],invfac[N+1],inv[N+1],sz[N+1],ans;
vector<int>E[N+1];
vector<int>st[N+1];
int MD(int x)
{
return (x>=mod)?x-mod:x;
}
void Adder(int &x,int d)
{
x+=d;
if (x>=mod) x-=mod;
return;
}
struct seg
{
struct node
{
int l,r,ls,rs,data,lazy,lazy2;
};
node tree[100*N+1];
int length;
int new_node(int l,int r)
{
tree[++length]=(node){l,r,0,0,0,1,0};
return length;
}
void spread(int x)
{
if (tree[x].lazy!=1||tree[x].lazy2)
{
tree[tree[x].ls].data=MD(1ll*tree[tree[x].ls].data*tree[x].lazy%mod+1ll*(tree[tree[x].ls].r-tree[tree[x].ls].l+1)*tree[x].lazy2%mod);
tree[tree[x].ls].lazy=1ll*tree[tree[x].ls].lazy*tree[x].lazy%mod;
tree[tree[x].ls].lazy2=MD(1ll*tree[tree[x].ls].lazy2*tree[x].lazy%mod+tree[x].lazy2);
tree[tree[x].rs].data=MD(1ll*tree[tree[x].rs].data*tree[x].lazy%mod+1ll*(tree[tree[x].rs].r-tree[tree[x].rs].l+1)*tree[x].lazy2%mod);
tree[tree[x].rs].lazy=1ll*tree[tree[x].rs].lazy*tree[x].lazy%mod;
tree[tree[x].rs].lazy2=MD(1ll*tree[tree[x].rs].lazy2*tree[x].lazy%mod+tree[x].lazy2);
}
tree[x].lazy=1,tree[x].lazy2=0;
return;
}
void push_up(int x)
{
tree[x].data=MD(tree[tree[x].ls].data+tree[tree[x].rs].data);
return;
}
int merge(int x,int y)
{
if (!tree[x].ls&&tree[y].ls) swap(x,y);
if (!tree[y].ls) Adder(tree[x].data,tree[y].data),Adder(tree[x].lazy2,tree[y].lazy2);
else spread(x),spread(y),tree[x].ls=merge(tree[x].ls,tree[y].ls),tree[x].rs=merge(tree[x].rs,tree[y].rs),push_up(x);
return x;
}
void add(int x,int l,int r,int d,int d2)
{
if (l>r) return;
if (tree[x].l==l&&tree[x].r==r)
{
tree[x].data=MD(1ll*tree[x].data*d%mod+1ll*(tree[x].r-tree[x].l+1)*d2%mod);
tree[x].lazy=1ll*tree[x].lazy*d%mod;
tree[x].lazy2=MD(1ll*tree[x].lazy2*d%mod+d2);
return;
}
int mid=(tree[x].l+tree[x].r)>>1;
if (!tree[x].ls) tree[x].ls=new_node(tree[x].l,mid);
if (!tree[x].rs) tree[x].rs=new_node(mid+1,tree[x].r);
spread(x);
if (r<=mid) add(tree[x].ls,l,r,d,d2);
else if (l>=mid+1) add(tree[x].rs,l,r,d,d2);
else add(tree[x].ls,l,mid,d,d2),add(tree[x].rs,mid+1,r,d,d2);
push_up(x);
return;
}
int query(int k,int x)
{
if (tree[k].l==tree[k].r) return tree[k].data;
int mid=(tree[k].l+tree[k].r)>>1;
if (!tree[k].ls) tree[k].ls=new_node(tree[k].l,mid);
if (!tree[k].rs) tree[k].rs=new_node(mid+1,tree[k].r);
spread(k);
if (x<=mid) return query(tree[k].ls,x);
else return query(tree[k].rs,x);
}
};
seg T;
bool cmp(int x,int y)
{
return minn[x]<minn[y];
}
void dfs(int x)
{
int res=0;
minn[x]=a[x],sz[x]=1,used[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i]])
dfs(E[x][i]),sz[x]+=sz[E[x][i]],minn[x]=min(minn[x],minn[E[x][i]]),st[x].push_back(E[x][i]),rts[x]=T.merge(rts[x],rts[E[x][i]]);
res=sz[x]-1,sort(st[x].begin(),st[x].end(),cmp);
for (int i=0;i+1<st[x].size();++i) res-=sz[st[x][i]],T.add(rts[x],minn[st[x][i]]+1,minn[st[x][i+1]],inv[i+1],1ll*inv[i+2]*res%mod);
if (!st[x].empty()) T.add(rts[x],minn[st[x].back()]+1,inf,inv[st[x].size()],0);
T.add(rts[x],minn[x]+1,inf,1,1);
T.add(rts[x],a[x]+1,inf,0,0);
Adder(ans,(T.tree[rts[x]].data+1ll*minn[x]*sz[x]%mod)%mod);
return;
}
int main()
{
int ST=read(),x,y;
while (ST--)
{
n=read(),rt=read(),T.length=ans=0,fac[0]=1;
for (int i=1;i<=n;++i) E[i].clear(),st[i].clear(),used[i]=0,rts[i]=T.new_node(1,inf),fac[i]=1ll*fac[i-1]*i%mod;
invfac[n]=fast_pow(fac[n],mod-2);
for (int i=n-1;i>=0;--i) invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
for (int i=1;i<=n;++i) inv[i]=1ll*fac[i-1]*invfac[i]%mod;
for (int i=1;i<=n;++i) a[i]=read();
for (int i=1;i<=n-1;++i) x=read(),y=read(),E[x].push_back(y),E[y].push_back(x);
dfs(rt),printf("%d\n",ans);
}
return 0;
}