专栏文章

CF2071E LeaFall 题解 分类讨论

DDemoe
CF2071E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miptraza
此快照首次捕获于
2025/12/03 17:48
3 个月前
此快照最后确认于
2025/12/03 17:48
3 个月前
查看原文
题目传送门\large\text{题目传送门}

Description\text{Description}

  • 给定一棵 nn 个节点的树，每个节点有 piqi\dfrac{p_i}{q_i} 的概率坍塌（指切断所有邻边）。
  • 求期望的无序叶子节点对数。（其中叶子节点指恰有一条邻边的节点）
  • 答案对 998244353998244353 取模。
  • 多测。

Solution\text{Solution}

记 N(k)N(k) 为 kk 在树上的相邻节点集，dis(i,j)dis(i,j) 为树上 ii 与 jj 路径的边数，简记 pip_i 为 ii 号节点坍塌的概率。
首先考虑每个节点成为叶子节点的概率，由题可写出 vi=(1−pi)∑j∈N(i)(1−pj)∏k∈N(i)&k≠jpk=(1−pi)(∏k∈N(i)pk)(∑j∈N(i)1−pjpj)v_i=(1-p_i)\sum\limits_{j\in N(i)}(1-p_j)\prod\limits_{k\in N(i) \& k\neq j}p_k=(1-p_i)(\prod\limits_{k\in N(i)}p_k)(\sum\limits_{j\in N(i)}\dfrac{1-p_j}{p_j})。

Warning\text{Warning}

期望点对数不可直接由期望点数求出。
Node=∑piaiNode=\sum p_i a_i
Pair=∑piai2−ai2≠Node2−Node2Pair=\sum p_i \dfrac{a_i^2-a_i}{2}\neq \dfrac{Node^2-Node}{2}
因此我们只可直接考虑点对。
考虑到 dis(i,j)≥3dis(i,j)\ge 3 时，两点各自为叶子节点的两事件独立，而 dis(i,j)=1dis(i,j)=1 和 dis(i,j)=2dis(i,j)=2 的情况下，由于存在邻居节点重合事件不独立，需要另外考虑。
因此做出如下分讨：

dis(i,j)≥3dis(i,j)\ge 3

由于独立，贡献为 vi×vjv_i\times v_j。

dis(i,j)=1dis(i,j)=1

显然 ii 和 jj 都不能坍塌，则若 (i,j)(i,j) 要成为叶子点对，其连边则为唯一边，也即 ii 和 jj 的其余所有邻居节点坍塌。
贡献为 (1−pi)(1−pj)∏k∈N(i)∪N(j)&k≠i,jpk(1-p_i)(1-p_j)\prod\limits_{k\in N(i)\cup N(j)\& k\neq i,j}p_k。

dis(i,j)=2dis(i,j)=2

考虑 ii 与 jj 路径上的唯一点 kk。
若 kk 不坍塌，则 (i,j)(i,j) 要成为叶子点对，则除 kk 以外的 ii 与 jj 的邻居节点全部坍塌。
此处贡献为 (1−pi)(1−pj)(1−pk)∏s∈N(i)∪N(j)&s≠kps(1-p_i)(1-p_j)(1-p_k)\prod\limits_{s\in N(i)\cup N(j)\& s\neq k}p_s。
若 kk 坍塌，则 (i,j)(i,j) 要成为叶子点对，则各有一个邻居节点未坍塌。
此处贡献为 pk(1−pi)(1−pj)(∑s∈N(i)&s≠k(1−ps)∏t∈N(i)&t≠k,spt)(∑s∈N(j)&s≠k(1−ps)∏t∈N(j)&t≠k,spt)p_k(1-p_i)(1-p_j)(\sum\limits_{s\in N(i)\& s\neq k}(1-p_s)\prod\limits_{t\in N(i)\& t\neq k,s}p_t)(\sum\limits_{s\in N(j)\& s\neq k}(1-p_s)\prod\limits_{t\in N(j)\& t\neq k,s}p_t)。
两者加和即可。
考虑如何快速计算贡献。
令 Ai=∏j∈N(i)pjA_i=\prod\limits_{j\in N(i)}p_j，Bi=∑j∈N(i)1−pjpjB_i=\sum\limits_{j\in N(i)}\dfrac{1-p_j}{p_j}。
两者都可以在输入的时候顺带线性处理。
  • dis(i,j)≥3dis(i,j)\ge 3
    vi=(1−pi)AiBiv_i=(1-p_i)A_iB_i。
    可以先利用前缀和线性计算 ∑i=1n∑j=i+1nvi×vj\sum\limits_{i=1}^n\sum\limits_{j=i+1}^nv_i\times v_j，然后再在计算 dis(i,j)=1dis(i,j)=1 和 dis(i,j)=2dis(i,j)=2 的时候将多计算的部分剔除。
  • dis(i,j)=1dis(i,j)=1
    枚举边即可线性计算 (1−pi)(1−pj)∏k∈N(i)∪N(j)&k≠i,jpk=(1−pi)(1−pj)pipjAiAj(1-p_i)(1-p_j)\prod\limits_{k\in N(i)\cup N(j)\& k\neq i,j}p_k=\dfrac{(1-p_i)(1-p_j)}{p_ip_j}A_iA_j。
  • dis(i,j)=2dis(i,j)=2
    对每个 kk，
    分别计算 (1−pi)(1−pj)(1−pk)∏s∈N(i)∪N(j)&s≠kps(1-p_i)(1-p_j)(1-p_k)\prod\limits_{s\in N(i)\cup N(j)\& s\neq k}p_s 和 pk(1−pi)(1−pj)(∑s∈N(i)&s≠k(1−ps)∏t∈N(i)&t≠k,spt)(∑s∈N(j)&s≠k(1−ps)∏t∈N(j)&t≠k,spt)p_k(1-p_i)(1-p_j)(\sum\limits_{s\in N(i)\& s\neq k}(1-p_s)\prod\limits_{t\in N(i)\& t\neq k,s}p_t)(\sum\limits_{s\in N(j)\& s\neq k}(1-p_s)\prod\limits_{t\in N(j)\& t\neq k,s}p_t)，
    可分别简记为 1−pkpk2(1−pi)Ai(1−pj)Aj\dfrac{1-p_k}{p_k^2}(1-p_i)A_i(1-p_j)A_j 和 1pk(1−pi)Ai(Bi−1−pkpk)(1−pj)Aj(Bj−1−pkpk)\dfrac{1}{p_k}(1-p_i)A_i(B_i-\dfrac{1-p_k}{p_k})(1-p_j)A_j(B_j-\dfrac{1-p_k}{p_k})。
    由于 ii 与 jj 在贡献中对称，易发现可以类似 dis(i,j)≥3dis(i,j)\ge 3 的方式计算前缀和线性得。

Time Complexity\text{Time Complexity}

计算逆元时间复杂度为 O(log⁡M)O(\log M)，每部分遍历都是线性的，因此总时间复杂度为 O(nlog⁡M)O(n\log M)。

Space Complexity\text{Space Complexity}

记录树以及每个节点的不同权值即可，O(n)O(n)。

Code\text{Code}

CPP
const int N=1e5+5,mod=998244353;
int t,n,p[N],v[N],A[N],B[N];
vector<int> e[N];

inline int pw(int x,int y){
	int sum=1;
	while(y){
		if(y&1) sum=1ll*sum*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return sum;
}

inline int inv(int x){return pw(x,mod-2);}

inline void solve(){
	rd(n);int sum1=0,sum21=0,sum22=0,sum3=0;
	for(re i=1;i<=n;++i){
		int q;rd(p[i]);rd(q);p[i]=1ll*p[i]*inv(q)%mod;
		e[i].clear();A[i]=1;B[i]=0;
	}
	for(re i=1;i<n;++i){
		int u,v;rd(u);rd(v);
		e[u].pb(v);e[v].pb(u);
		A[u]=1ll*A[u]*p[v]%mod;A[v]=1ll*A[v]*p[u]%mod;
		B[u]=(1ll*(1-p[v]+mod)%mod*inv(p[v])%mod+B[u])%mod;B[v]=(1ll*(1-p[u]+mod)%mod*inv(p[u])%mod+B[v])%mod;
	}
	for(re i=1;i<=n;++i) v[i]=1ll*(1-p[i]+mod)%mod*A[i]%mod*B[i]%mod;
	int tmp=0;
	for(re i=1;i<=n;++i) sum3=(sum3+1ll*tmp*v[i]%mod)%mod,tmp=(tmp+v[i])%mod;
	for(re i=1;i<=n;++i)
		for(re j=0;j<e[i].size();++j)
			if(i<e[i][j]){
				sum1=(sum1+1ll*(1-p[i]+mod)%mod*(1-p[e[i][j]]+mod)%mod*inv(p[i])%mod*inv(p[e[i][j]])%mod*A[i]%mod*A[e[i][j]]%mod)%mod;
				sum3=(sum3-1ll*v[i]*v[e[i][j]]%mod+mod)%mod;
			}
	for(re i=1;i<=n;++i){
		int tmp1=0,tmp2=0,tmp3=0,p1=1ll*(1-p[i]+mod)%mod*inv(p[i])%mod*inv(p[i])%mod,p2=inv(p[i]),p3=1ll*(1-p[i]+mod)%mod*inv(p[i])%mod;
		for(re j=0;j<e[i].size();++j){
			sum21=(sum21+1ll*tmp1*(1-p[e[i][j]]+mod)%mod*A[e[i][j]]%mod*p1%mod)%mod;tmp1=(tmp1+1ll*(1-p[e[i][j]]+mod)%mod*A[e[i][j]]%mod)%mod;
			sum22=(sum22+1ll*tmp2*(1-p[e[i][j]]+mod)%mod*A[e[i][j]]%mod*(B[e[i][j]]-p3+mod)%mod*p2%mod)%mod;tmp2=(tmp2+1ll*(1-p[e[i][j]]+mod)%mod*A[e[i][j]]%mod*(B[e[i][j]]-p3+mod)%mod)%mod;
			sum3=(sum3-1ll*tmp3*v[e[i][j]]%mod+mod)%mod;tmp3=(tmp3+v[e[i][j]])%mod;
		}
	}
	wr((sum1+(sum21+(sum22+sum3)%mod)%mod)%mod);puts("");
}

// ---------- sum ---------- //

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...