自动搬运

查看原文

来自洛谷，原作者为

	xtx1092515503 Mathematics compares the most diverse phenomena, and discovers the secret analogies which unite them. @Joseph Fourier

搬运于2025-08-24 22:38:07，当前版本为作者最后更新于2022-05-11 16:23:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

考虑关于每个权值分开处理：对于权值 $V$，我们计算 $\min\geq V$ 的概率，则对每个 $V$ 的概率求和即得到最终期望。

对于某个 $V$，我们记 $\geq V$ 的位置为 黑点，$<V$ 的位置为 白点。

考虑针对路径 $x\to y$ 计算答案。

模拟 dfs 的流程，就能发现，一旦我们进入到某棵 存在白点的子树，则这次搜索就不合法了。

考虑当前在节点 $u$。记除去 $y$ 所在的子树外，$u$ 还有 $c_u$ 棵存在白点的子树，$d_u$ 棵全黑子树。

在前往 $y$ 所在的子树前不经过任何存在白点的子树的概率是多少呢？

考虑随机一组排列，按照这种顺序访问每棵子树。则，$y$ 所在子树在每个位置被访问的概率均相同，即为 $\dfrac1{c_u+d_u+1}$。

其在第 $i$ 个位置被访问前不经过任何白子树的概率是 $\dfrac{d_u^{\underline{i-1}}}{(c_u+d_u)^{\underline{i-1}}}$，则我们要计算 $\dfrac1{c_u+d_u+1}\sum\limits_{i=1}^{c_u+d_u+1}\dfrac{d_u^{\underline{i-1}}}{(c_u+d_u)^{\underline{i-1}}}$。

稍微推一下式子吧！

$$\dfrac1{c_u+d_u+1}\sum\limits_{i=1}^{c_u+d_u+1}\dfrac{d_u^{\underline{i-1}}}{(c_u+d_u)^{\underline{i-1}}} \\=\dfrac{d_u!}{(c_u+d_u+1)(c_u+d_u)!}\sum\limits_{i=1}^{d_u+1}\dfrac{(c_u+d_u+1-i)!}{(d_u-i+1)!} \\=\dfrac{d_u!c_u!}{(c_u+d_u+1)(c_u+d_u)!}\sum\limits_{i=1}^{d_u+1}\dfrac{(c_u+d_u+1-i)!}{(d_u-i+1)!c_u!} \\=\dfrac{\sum\limits_{i=1}^{d_u+1}\dbinom{c_u+d_u+1-i}{c_u}}{(c_u+d_u+1)\dbinom{c_u+d_u}{c_u}} \\=\dfrac{\sum\limits_{i=c_u}^{c_u+d_u}\dbinom{i}{c_u}}{(c_u+d_u+1)\dbinom{c_u+d_u}{c_u}} \\=\dfrac{\dbinom{c_u+d_u+1}{c_u+1}}{(c_u+d_u+1)\dbinom{c_u+d_u}{c_u}} \\=\dfrac1{c_u+1} $$

而这个式子是很符合直觉的，因为事实上我们摇到纯黑子树可以相当于做了无效决策，故只需找到 $y$ 所在子树在所有非纯黑子树前摇到的概率即可，而该概率即为上式。

令 $f_u$ 表示上式与 $[u\text{是黑点}]$ 的积，则 $w(x\to y)=[y\text{是黑点}]\prod\limits_{z\in[x\to y)}f_z$，其中 $z$ 枚举到 $x$，不枚举到 $y$。

但是我们发现，对于同一个 $u$ 和不同的 $y$，$c_u$ 可能是不同的（因为 $c_u$ 并不包含 $y$ 所在子树），故 $f_u$ 也是不同的。

但是再注意到对于纯黑子树和非纯黑子树，它们对应的 $c_u$ 各自是相同的。故我们只需对 $y$ 所在子树是 $u$ 的纯黑子树还是非纯黑子树分别讨论一下即可。

到现在，我们已经会一个若干方的垃圾做法了，考虑进一步做点操作。

令 $dp_i$ 表示，$x=i$ 且 $y$ 为 $i$ 子树中全体点时，$\sum w(x\to y)$。则权值为 $c$ 时的答案即为 $\sum dp_i$。

考虑用 $w$ 的式子来推出 DP。然后我们发现 $dp_x=[x\text{是黑点}]+\sum\limits_{y\in\text{son}_x}dp_yf_{x,y}$，其中 $f_{x,y}$ 为 $y$ 所在子树与 $x$ 间的 $f$ 值。

这个式子允许我们在线性时间内对一个权值 $V$ 求解。

现在我们要对多个 $V$ 求解。考虑 $V$ 不同时上述条件的变化。

$V$ 不同时，仅有节点颜色会变化。记 $b_x$ 为节点 $x$ 的颜色，其在 $x$ 为黑时等于一，$x$ 为白时等于零。

考虑从大往小对 $V$ 做扫描线。则，所有 $b_x$ 都只会由白翻黑一次，所有子树都会由非纯黑翻成纯黑一次。因为只有这两个信息会影响我们的转移式，所以自然想到用 DDP 维护这个式子。

可以使用全局平衡二叉树搞，但是我不会。

djq 神仙教我了一种用树剖做到 $O(n\log n)$ DDP 的方法。

upd: 这就是全局平衡二叉树。学过的人就直接忽略这一段吧。

树剖的 $\log$ 肯定是免不了的。关键是线段树的 $\log$ 能不能省掉呢？

我们把每条重链拎出来单独建一棵线段树。但是这里的线段树比较奇葩：其在 轻子树大小折半 处分裂。

也即，考虑重链上每个节点的权重为其轻子树大小和，则我们在节点下方的权重和恰为总权重和一半的位置把区间分开。

可以发现，在线段树上每跳一步，其管辖的轻子树大小和就会翻倍；在树剖上每跳一步，轻子树大小也会翻倍；故总跳跃次数是 $O(\log n)$ 的。

折半的位置可以在建树时预处理出来。

我们考虑把转移式写成 $dp_x=K_xdp_{son_x}+B_x$，其中 $K,B$ 是由轻儿子维护的信息。这个东西显然是可以用线段树维护的。然后还要额外记一个 $DP_x=\sum dp_x$，这玩意可以另外开一个二元组维护。最后我们每个节点上需要记四个值。

如果一个点由白翻黑，则 $f$ 值会变化（因为 $f_u=\dfrac{b_u}{c_u+1}$），且转移式也会变化（$dp_x$ 的转移式中也有 $b$）。

如果一个子树由非全黑翻成全黑，则 $f$ 值会变化，且对于全黑子树和非全黑子树变动还不一样（因为它们对应的 $f$ 也不一样）。

怎么办呢？当 $f$ 变化时，重儿子的 $f$ 以及 DP 转移式的变化可以暴力在线段树上修改四元组；轻儿子的 $f$ 变化可以分全黑轻儿子和非全黑轻儿子分开搞。

故大力写就完事了。

复杂度 $O(n\log n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
void read(int&x){
	x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
void print(int x){if(x>=10)print(x/10);putchar('0'+x%10);}
const int N=400100;
const int mod=998244353;
void ADD(int&x,int y){if((x+=y)>=mod)x-=mod;}
int T,n,RT,a[N],b[N],m,INV[N],res;
int dfn[N],rev[N],top[N],bot[N],son[N],fa[N],dep[N],sz[N],tot;
bool col[N],asc[N];int c[N];
vector<int>v[N],w[N];
void dfs1(int x){
	dep[x]=dep[fa[x]]+1,sz[x]=1,son[x]=0;
	for(auto y:v[x])if(y!=fa[x]){fa[y]=x,dfs1(y),sz[x]+=sz[y];if(sz[y]>sz[son[x]])son[x]=y;}
}
void dfs2(int x){
	dfn[x]=++tot,rev[tot]=x;bot[top[x]]=x;
	if(son[x])top[son[x]]=top[x],dfs2(son[x]);
	for(auto y:v[x])if(y!=fa[x]&&y!=son[x])top[y]=y,dfs2(y);
}
int lid[N][2],lis[N];
struct dat{
int kd,bd,ks,bs;
dat(){kd=bd=ks=bs=0;}
dat(int KD,int BD,int KS,int BS){kd=KD,bd=BD,ks=KS,bs=BS;}
friend dat operator*(const dat&u,const dat&v){
	dat w;
	w.kd=1ll*u.kd*v.kd%mod,w.bd=(1ll*u.kd*v.bd+u.bd)%mod;
	w.ks=(1ll*u.ks*v.kd+v.ks)%mod,w.bs=(1ll*u.ks*v.bd+u.bs+v.bs)%mod;
	return w;
}
};
int cnt,rt[N];
#define lson seg[x].ch[0]
#define rson seg[x].ch[1]
struct SegTree{int ch[2],l,r;dat tr;}seg[N<<3];
void build(int&x,int l,int r){
	x=++cnt,seg[x].l=l,seg[x].r=r,seg[x].tr=dat();
	if(l==r)return;
	int L=l+1,R=r,B=(rev[r]==bot[top[rev[r]]]?0:sz[rev[r+1]]);
	while(L<R){
		int mid=(L+R+1)>>1;
		if(sz[rev[l]]-sz[rev[mid]]<sz[rev[mid]]-B)L=mid;else R=mid-1;
	}
	build(lson,l,R-1),build(rson,L,r);
}
void reset(int x,int P,dat val){
	if(seg[x].l==seg[x].r){seg[x].tr=val;return;}
	P<=seg[lson].r?reset(lson,P,val):reset(rson,P,val),seg[x].tr=seg[lson].tr*seg[rson].tr;
}
void account(int x,int tp){
	if(top[x]==RT)return;
	int dp=seg[rt[top[x]]].tr.bd,dps=seg[rt[top[x]]].tr.bs;
	if(tp==1)ADD(lid[fa[top[x]]][asc[top[x]]],dp),ADD(lis[fa[top[x]]],dps);
	else ADD(lid[fa[top[x]]][asc[top[x]]],mod-dp),ADD(lis[fa[top[x]]],mod-dps);
}
void reset(int x){
	int dp=(col[x]?(1ll*lid[x][0]*INV[c[x]]+1ll*lid[x][1]*INV[c[x]+1]+1)%mod:0);
	int dps=(lis[x]+dp)%mod;
	reset(rt[top[x]],dfn[x],dat(col[x]*INV[c[x]+asc[son[x]]],dp,col[x]*INV[c[x]+asc[son[x]]],dps));
}
void flip(int x){
	for(int i=x;i;i=fa[top[i]])account(i,-1);
	col[x]=true;
	for(int i=x;i;i=fa[top[i]])reset(i),account(i,1);
	while(x!=RT&&!c[x]&&col[x]){
		int y=(son[fa[x]]==x?fa[x]:x);
		for(int i=y;i;i=fa[top[i]])account(i,-1);
		asc[x]=true,c[fa[x]]--;
		for(int i=y;i;i=fa[top[i]])reset(i),account(i,1);
		x=fa[x];
	}
}
void mina(){
	read(n),read(RT),cnt=res=0;
	INV[1]=1;for(int i=2;i<=n;i++)INV[i]=1ll*INV[mod%i]*(mod-mod/i)%mod;
	for(int i=1;i<=n;i++)read(a[i]),b[i]=a[i];
	sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)w[lower_bound(b+1,b+m+1,a[i])-b].push_back(i);
	for(int i=1,x,y;i<n;i++)read(x),read(y),v[x].push_back(y),v[y].push_back(x);
	dep[RT]=fa[RT]=0,dfs1(RT),top[RT]=RT,dfs2(RT),tot=0;
	for(int i=1;i<=n;i++)if(top[i]==i)build(rt[i],dfn[i],dfn[bot[i]]);
	for(int i=1;i<=n;i++)col[i]=asc[i]=false,lid[i][0]=lid[i][1]=lis[i]=0;
	for(int i=1;i<=n;i++)if(i!=RT)c[fa[i]]++;
	for(int i=m;i;i--){
		for(auto x:w[i])flip(x);w[i].clear();
		res=(1ll*seg[rt[RT]].tr.bs*(b[i]-b[i-1])+res)%mod;
	}
	print(res),putchar('\n');
	for(int i=1;i<=n;i++)v[i].clear();
}
int main(){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	read(T);
	while(T--)mina();
	return 0;
}