专栏文章

题解：AT_agc073_c [AGC073C] Product of Max of Sum of Subtree

eemmoy
AT_agc073_c题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minpjemh
此快照首次捕获于
2025/12/02 06:15
3 个月前
此快照最后确认于
2025/12/02 06:15
3 个月前
查看原文

题目大意

有一棵 nn 个点的树，考虑给每个点均匀随机一个在 [−(n−1),1][-(n-1),1] 之间的实数。
对于每个点 xx，定义 pxp_x 为树上包含点 xx 的联通块的最大权值和。
定义这棵树的贡献为，若 ∀i,0⩽px⩽1\forall i,0\leqslant p_x\leqslant1，则贡献为 ∏i=1npi\prod_{i=1}^np_i，否则贡献为 00。
求贡献的期望。

解法

为了区分取值范围与点数，设取值范围为 lenlen，易知 len=nlen=n。
先考虑一个弱化问题：若整棵树的 pp 值相等，求贡献的期望。
不妨设整棵树的 pp 值为 ff，易知 f∈[0,1]f\in[0,1] 时贡献非零。
设 sxs_x 表示 xx 的子树中所有随机权值的和，由于若 sx<0s_x<0，则抛弃掉这颗子树显然更优，而又由于 sx⩽fs_x\leqslant f，所以 sxs_x 的取值范围为 sx∈[0,f]s_x\in[0,f]。
因为一种随机方案与一种 sxs_x 的方案唯一对应，由于要求 s1=fs_1=f，所以序列 ss 合法的概率为 fn−1lennf^{n-1}\over len^n，所以树的期望贡献为：
∫01xn−1lennxn\int_0^1{x^{n-1}\over len^n}x^n
简单化简一下：
∫01xn−1lennxn=1lenn∫01xn−1xn=1lenn∫01x2n−1=1lenn(12n2n−02n2n)=1lenn×12n\begin{aligned} &\int_0^1{x^{n-1}\over len^n}x^n\\ =&{1\over len^n}\int_0^1x^{n-1}x^n\\ =&{1\over len^n}\int_0^1x^{2n-1}\\ =&{1\over len^n}\left({1^{2n}\over2n}-{0^{2n}\over 2n}\right)\\ =&{1\over len^n}\times{1\over2n} \end{aligned}
再考虑原问题。
容易发现，我们可以把树分为许多值相同的联通块，对于一个联通块可以用上述方法去做，且可以做到联通块之间互不影响。
若两点 xx 与 yy 属于不同联通块，不妨设 xx 所在联通块的 fxf_x 大于 yy 所在联通块的 fyf_y，那么我们给 yy 随机的权值减去 fxf_x 就行了，这样联通块就能互不重合了，fx⩽fyf_x\leqslant f_y 同理。因为最多减掉 n−1n-1，所以不会超出随机值下界。
然后就可以在树上 dp 了。
设 fx,if_{x,i} 表示 xx 的子树中 xx 所在的联通块大小，i=0i=0 表示该联通块已计算完贡献。
转移是平凡的，由于所有联通块大小的和一定为 nn，于是 dp 完后再乘上 1lenn1\over len^n 就行了。
时间复杂度 O(n2)\mathcal{O}(n^2)。
CodeCPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+10;
const int p=998244353;
int n,m,inv[100010];
int f[N][N],sz[N],h[N];
vector<int> g[N];
int mo(int x){return x>=p?x-p:x;}
void add(int&x,int y) {x=mo(x+y);}
int ksm(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=a*a%p) if(b&1) ans=ans*a%p;
	return ans;
}
void dfs(int x,int fa){
	sz[x]=1;
	f[x][1]=1;
	for(int v:g[x]){
		if(v==fa) continue;
		dfs(v,x);
		for(int i=1;i<=sz[x];i++)
			for(int j=0;j<=sz[v];j++)
				add(h[i+j],f[x][i]*f[v][j]%p);
		sz[x]+=sz[v];
		for(int i=1;i<=sz[x];i++) f[x][i]=h[i],h[i]=0;
	}
	for(int i=1;i<=sz[x];i++) add(f[x][0],f[x][i]*inv[i*2]%p);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	inv[1]=1;
	for(int i=2;i<=n*2;i++) inv[i]=(p-p/i)*inv[p%i]%p;
	for(int i=1,x,y;i<n;i++) cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
	dfs(1,0);
	cout<<f[1][0]*ksm(ksm(n,n),p-2)%p<<"\n";
	return 0;
}

评论

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

正在加载评论...