专栏文章

题解：AT_agc058_f [AGC058F] Authentic Tree DP

iinclude13_fAKe
AT_agc058_f题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minh9a8f
此快照首次捕获于
2025/12/02 02:23
3 个月前
此快照最后确认于
2025/12/02 02:23
3 个月前
查看原文
不朽的思维题！
本题解会使用 CF Hint 的风格。
Hint 1
如果把 1n\frac{1}{n} 换成 1n−1\frac{1}{n-1} 应该怎么做？
答案
对于任意树，f(t)=1f(t)=1。
证明思路
完全归纳法。
对于单点，f(t)=1f(t)=1。
对于大小为 22 的树，将其拆成两个单点，得 f(t)=1f(t)=1。
……
对于大小为 nn 的树，沿任意一条边分割成两部分，这两部分均满足 f=1f=1，所以答案为 (n−1)×1n−1×1×1=1(n-1)\times \frac{1}{n-1}\times 1\times 1=1。
Hint 2
如何通过改动树的形态，使其能够利用 1n−1\frac{1}{n-1} 在上轮计算的特性解决原问题？
尝试
首先，只在每一个边上建一个点的思路是不优的。因为树的总结点数会变成 2n−12n-1。其他很多题解都说要给这些在边上建的点各连 −1-1 个点，点数恢复至 nn。若不好理解可换成 p−1p-1 个点（下文均使用连 p−1p-1 个点的情况)。因为它们模 pp 的余数是相等的！
考虑随机一个长度为 (n−1)p+n(n-1)p+n 的排列，求边上建立的点的权值大于周围所有点（包括原树点和其他的新增点）的概率。
为什么转换后的答案与转换前相同？
令新的树为 WW，原树为 TT。新的答案为 g(W)g(W)，原答案为 f(T)f(T)。
当树为单点时，显然 g(W)=f(T)g(W)=f(T)。树不为单点时，可以使用类似于上文 1n−1\frac{1}{n-1} 的证明思路。
Hint 3
考虑用树上背包解决，并加入容斥思路。
最终解法
令 dpu,idp_{u,i} 代表节点 uu 的外向树大小为 ii 的概率。
以边上新增点为父亲的那 p−1p-1 个新点
仅有 dpu,1=1dp_{u,1}=1。
边上新增点
为什么我们最开始说的是连 −1-1 个点？是因为无论是连 −1-1 个点还是连 p−1p-1 个点都会使 sizeusize_u 和 uu 的儿子中唯一在原树上的点 vv 的 sizesize 一致。
dpudp_u 仅需继承 dpvdp_v 即可。但要再乘以一个 1i\frac{1}{i}。因为要保证目前点的答案最大。
原树点
容斥。
将边从父亲指向儿子改成删除边减去儿子指向父亲。
删除边需要满足子树 vv 合法，fu,i=fu,i×∑fv,jf_{u,i}=f_{u,i}\times \sum f_{v,j}。
接着就是减去儿子指向父亲的情况，fu,i+j=fu,i+j−fu,i×fv,jf_{u,i+j}=f_{u,i+j}-f_{u,i}\times f_{v,j}。通过改变转移顺序可以节省一倍空间。
还是要乘上 1i\frac{1}{i}。因为还是有这里最大值的要求。
最终答案：∑f1,i\sum f_{1,i}。
时间复杂度 O(n2)O(n^2)。需要预处理逆元。
代码CPP
#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
}
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48); 
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');
}
const int N=3*2025;
const int mod=998244353;
inline int qpow(int x,int y){
	if(x==0)	return 0;
	if(y==0)	return 1;
	if(y==1)	return x;
	int ret=qpow(x,y/2);
	ret=ret*ret%mod;
	if(y&1)	ret=ret*x%mod;
	return ret;
}
int inv_[N];
inline int inv(int x){
	if(inv_[x])	return inv_[x];
	return inv_[x]=qpow(x,mod-2);
}
vector<int> g[N];
int dp[N][N];	//dp[u][i] 代表子树 u 有 i 的大小的概率 
int siz[N]; 
int fa[N];
int n;
void DP(int u){
	siz[u]=1;
	dp[u][1]=1;	//代表这里有 1 个的概率为 100% 
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(fa[u]==v)	continue;
		fa[v]=u;
		DP(v);
		int sum=0;
		for(int j=siz[u];j>=0;j--){
			sum=0;
			for(int k=siz[v];k>=0;k--){
				dp[u][j+k]-=dp[u][j]*dp[v][k]%mod*inv(k)%mod;
				dp[u][j+k]+=mod;
				dp[u][j+k]%=mod;
				sum+=dp[v][k]*inv(k)%mod;
				sum%=mod;
			}
			dp[u][j]=dp[u][j]*sum%mod;
		}
		siz[u]+=siz[v];
	} 
	for(int i=1;i<=siz[u];i++){
		dp[u][i]=dp[u][i]*inv(i)%mod;
	}
} 
#undef int
int main(){
	#define int long long
//	cout<<qpow(3,11)<<endl; 
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		g[u].push_back(v),g[v].push_back(u);
	}
	DP(1);
	int include13=0;
	for(int i=1;i<=n;i++){
		include13+=dp[1][i];
		include13%=mod;
	}
	write2(include13);
	return 0; 
} //AGC058F CSP-S2025RP++

评论

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

正在加载评论...