[AGC058F] Authentic Tree DP 题解

题意：

对于一棵 $n$ 个节点的无根树 $T$，我们按如下方式定义函数 $f(T)$ ：

若 $n=1$ ，定义 $f(T) = 1$。

若 $n>1$ ，定义
$f(T) = \frac{\sum_{e\in T} f(T_1(e)) \times f(T_2(e))}{n}$
其中 $e$ 是 $T$ 中的一条边，$T_1(e),T_2(e)$ 表示 $T$ 切断 $e$ 后分裂成的两棵新的树。

现在给定一棵 $n~(2\le n\le 5000)$ 个节点的树 $T$，编号从 $1$ 到 $n$ 。

请输出 $f(T) \bmod 998244353$ 的值。

非常喵喵的思维+dp题。

注意到这个奇怪的定义式，如果把 $\frac{1}{n}$ 改成 $\frac{1}{n-1}$ ，那么它的组合意义是：

将一棵树随机删除一条边，再分为两棵子树分别进行这样的操作，最终整个图变成 $n$ 个独立点的概率。

显然这个概率是 $1$ 。考虑将题目的 $\frac{1}{n}$ 转化为 $\frac{1}{n-1}$ 的情况。

可以想到的是，$n$ 和 $n-1$ 最为紧密的联系，就是点数和边数。

考虑对每个边建一个边点，这样就有 $2n-1$ 个点，且组合意义变为了

将一棵树随机删除一个点，再分为两棵子树分别进行这样的操作，最终将整棵树删完的概率。

显然这个概率还是 $1$ 。

不过这并不符合题意（点数不一样）。那怎么样才能使得点数为 $n$ 呢？

接下来就是本题最为喵喵的人类智慧操作了：给每个边点连 $-1$ 个点，这样点数就是 $n$ 了。

由于我们求的是模 $P$ 意义下的答案，所以这 $-1$ 个点其实就是连 $P-1$ 个点。

点数的问题解决了，然而根据刚才的组合意义，我们会在删除边点的同时删除原树上的点。

于是我们需要强制钦定所有边点的删除顺序先于周围的点，

这样每次删除的时候所有分出来的树的大小都与原来树上对应部分的大小模 $P$ 意义下相等

考虑以删除顺序为每条边定向，即边点指向周围的点。

这样树上就有很多儿子指父亲，父亲指儿子的情况

考虑容斥，我们钦定每个儿子先于父亲的限制变成父亲先于儿子或不限制，这样就是一棵外向树了。

设 $f(i,j)$ 为 $i$ 所在子树钦定有边的外向树大小为 $j$ 时满足要求的概率。

对于原树上的点 $u$ ，每个儿子都是边点，那么枚举儿子 $v$ ，考虑
- 直接删掉，有
  $f_{\rm now}(u,i)\operatorname{\big\uparrow} f_{\rm pre}(u,i)\cdot \sum_{j=1}^{\mathrm{size}(v)} f(v,j)$
  这里 $\uparrow$ 表示增量。
- 变成上到下，有
  $f_{\rm now}(u,i+j) \operatorname{\big\uparrow} f_{\rm pre}(u,i+j) - f(u,i)\cdot f(v,j)$
  这里是因为钦定了一条边反向，所以系数为 $-1$ 。
对于边点 $u$ ，每条限制都是向下的，则
$f_{\rm now}(u,i + j)\operatorname{\big\uparrow} f_{\rm pre}(u,i+j) +f(u,i)\cdot f(v,j)$

最后，由于每个点 $u$ 在外向树中是第一个被删除的，所以

$f(u,i)\gets f(u,i)\cdot \frac{1}{i}$

不过边点还有 $P-1$ 个额外点。注意到，当前边点加上这些点的 $\mathrm{size}$ 为 $0$ 。

且这些点的 $f$ 值仅有 $f(u,1)=1$ ，而每个边点只会有一个儿子是原树上的点

因此这个边点最终的值就是那个唯一原树上的儿子，即

$f(u,i)\gets f(v,i)\cdot \frac{1}{i}$

那么这就是一个树上背包，直接转移即可。

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int P = 998244353;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= P ? x -= P : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e3 + 15))

vector<int> vec[N];
int n, inv[N], tmp[N], sz[N], f[N][N], g[N];
void dfs(int u, int fa)
{
    f[u][1] = 1; sz[u] = 1;
    for(int v : vec[u]) if(v != fa)
    {
        dfs(v, u);
        rep(i, 1, sz[u] + sz[v]) tmp[i] = f[u][i], f[u][i] = 0;
        rep(i, 1, sz[u]) rep(j, 1, sz[v])
            add(f[u][i + j], (P - tmp[i] * f[v][j] % P * inv[j] % P) % P);
        rep(i, 1, sz[u]) add(f[u][i], tmp[i] * g[v] % P);
        sz[u] += sz[v];
    }
    rep(i, 1, n)
    { 
        f[u][i] = f[u][i] * inv[i] % P;
        add(g[u], f[u][i] * inv[i] % P);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; inv[1] = 1;
    rep(i, 2, n) inv[i] = (P - P / i) * inv[P % i] % P;
    rep(i, 1, n - 1)
    {
        static int u, v; cin >> u >> v;
        vec[u].push_back(v); vec[v].push_back(u);
    }
    dfs(1, 0); int res = 0; 
    rep(i, 1, n) add(res, f[1][i]);
    cout << res << '\n';
    return 0;
}