题解：AT_agc058_f [AGC058F] Authentic Tree DP
include13_fAKe
·
·
题解
不朽的思维题！
本题解会使用 CF Hint 的风格。
::::info[Hint 1]
如果把 \frac{1}{n} 换成 \frac{1}{n-1} 应该怎么做？
:::success[答案]
对于任意树，f(t)=1。
:::
:::warning[证明思路]
完全归纳法。
对于单点，f(t)=1。
对于大小为 2 的树，将其拆成两个单点，得 f(t)=1。
……
对于大小为 n 的树，沿任意一条边分割成两部分，这两部分均满足 f=1，所以答案为 (n-1)\times \frac{1}{n-1}\times 1\times 1=1。
:::
::::
::::info[Hint 2]
如何通过改动树的形态，使其能够利用 \frac{1}{n-1} 在上轮计算的特性解决原问题？
:::warning[尝试]
首先，只在每一个边上建一个点的思路是不优的。因为树的总结点数会变成 2n-1。其他很多题解都说要给这些在边上建的点各连 -1 个点，点数恢复至 n。若不好理解可换成 p-1 个点（下文均使用连 p-1 个点的情况)。因为它们模 p 的余数是相等的！
考虑随机一个长度为 (n-1)p+n 的排列，求边上建立的点的权值大于周围所有点（包括原树点和其他的新增点）的概率。
:::
:::warning[为什么转换后的答案与转换前相同？]
令新的树为 W，原树为 T。新的答案为 g(W)，原答案为 f(T)。
当树为单点时，显然 g(W)=f(T)。树不为单点时，可以使用类似于上文 \frac{1}{n-1} 的证明思路。
:::
::::
:::::info[Hint 3]
考虑用树上背包解决，并加入容斥思路。
::::success[最终解法]
令 dp_{u,i} 代表节点 u 的外向树大小为 i 的概率。
:::success[以边上新增点为父亲的那 p-1 个新点]
仅有 dp_{u,1}=1。
:::
:::success[边上新增点]
为什么我们最开始说的是连 -1 个点？是因为无论是连 -1 个点还是连 p-1 个点都会使 size_u 和 u 的儿子中唯一在原树上的点 v 的 size 一致。
:::
:::success[原树点]
容斥。
将边从父亲指向儿子改成**删除边减去儿子指向父亲**。
删除边需要满足子树 $v$ 合法，$f_{u,i}=f_{u,i}\times \sum f_{v,j}$。
接着就是减去儿子指向父亲的情况，$f_{u,i+j}=f_{u,i+j}-f_{u,i}\times f_{v,j}$。通过改变转移顺序可以节省一倍空间。
还是要乘上 $\frac{1}{i}$。因为还是有这里最大值的要求。
:::
最终答案：$\sum f_{1,i}$。
时间复杂度 $O(n^2)$。需要预处理逆元。
::::
:::::
:::success[代码]
```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++
```
:::