E-嘿嘿嘿嘿嘿_一起来做题~欢乐赛7

题目描述

给你一棵n个节点的带标号无根树。每次，你可以选择一个度数为1的节点并将它从树上移除。问总共有多少种不同的方式能将这棵树删到只剩 1 个点。两种方式不同当且仅当至少有一步被删除的节点不同。

样例

算法1

(换根dp + 组合数学 + 树形背包问题)

前导

这个问题的简单版本就是将条件从求无根树变成求有根树
给你一棵n个节点的带标号有根树你可以选择一个度数为1的节点并将它从树上移除。问总共有多少种不同的方式能将这棵树删到只剩 1 个点。
那么问题是不是变成了求拓扑排序的个数，这两个问题是等价的。
简单版本我们可以用树形背包的思想
定义 $f[x]$ 表示以x为根的子树，拆除至最后剩x的方案数
根据树形背包的思考方式，我们从x的第一个儿子一直枚举到最后一个儿子
每次两两合并，将已经考虑过的子树看成一个整体与新考虑的子树求排列组合跟新答案，然后再将新考虑的子树加入到已考虑子树的集合中
这样每次只用考虑两个集合的情况
综合考虑两个集合的拆除节点的顺序可以看成是：
将两个序列合并，保证同一序列元素相对顺序不变
不同序列相互交叉排列形成一个更长的新序列的过程
不同序列内部的排列方式分别为 $f[x]$ 和 $f[j]$ （j表示新考虑的子树）
交叉方式为 $C_{sz[x] - 1 + sz[j]}^{sz[j]}$ ，sz[x] - 1 + sz[j]个位置选sz[j]个位置放进去（-1是因为根节点x一定是留到最后的）
$sz[x]$ 表示根节点x以及已经考虑的子树节点个数总和
$sz[j]$ 是新考虑的子树 $j$ 的节点个数
$sz[x] - 1$ 是因为根节点x是必定最后一个留下的所以不考虑在内
所以 $f[x] = \prod_{j} f[j] * C_{sz[x] - 1 + sz[j]}^{sz[j]}$
然后 $sz[x] += sz[j]$

分析

有根问题转化到无根问题我们考虑再原来的基础上使用换根dp的思想
我们先任选一个点作为根节点，用树形dp求一边有根问题的答案
然后考虑从这个点移动到其相邻点时答案时如何发生变化的
假设从节点x移动到其相邻节点j
我们考虑先将以 $j$ 为根节点的子树对答案的贡献剔除
注意我们每次考虑答案如何改变的时候都是从一个n个节点的集合（全集）中考虑的

换根dp

设从根节点u移动到其子节点v
先将v对答案的影响去掉，将去掉v影响的部分用 $f'[u]$ 表示

$f'[u] = f[u] / f[v] / C_{n - 1} ^ {sz[v]}$

解释： $f[u]$ 表示以u为根节点的答案， $f[v]$ 表示以v为根节点的子树的拆除顺序的序列个数

$C_{n - 1} ^ {sz[v]}$ 表示将以v为根节点的子树的拆除序列插入到总方案序列的方案数，(n - 1)是因为u一定是留到最后的
计算根转移到v后答案的变化

我们依然可以看成有两个序列合并，一个是以u 为根的树中除了以v为子树的节点外的节点的拆除序列，以及以v为子树的节点的拆除序列

换根后答案由 $f'[v]$ 表示

$f'[v] = f'[u] * f[v] * C_{n - 1}^{sz[v] - 1}$

解释： $sz[v] - 1$ 是因为v一定是留到最后的

细节：

模运算除法要用逆元

时间复杂度 $O(n)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define x first
#define y second

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 100010,mod = 998244353;
int h[N],ne[N * 2],e[N * 2],idx;
LL fac[N],inv[N];
LL f[N];
int sz[N];
LL ans;
int n;

LL qmi(LL a,int k)
{
    LL res = 1;
    a %= mod;
    while(k)
    {
        if(k & 1) res = (res * a) % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

void init()
{
    fac[0] = 1;
    for(int i = 1;i < N;i ++ ) fac[i] = fac[i - 1] * i % mod;
    inv[N - 1] = qmi(fac[N - 1],mod - 2);
    for(int i = N - 1;i;i --) inv[i - 1] = inv[i] * i % mod;
}

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

LL C(int a,int b)
{
    if(b > a) return 0;
    return fac[a] * inv[a - b] % mod * inv[b] % mod;
}

void dfs1(int u,int father)
{
    f[u] = 1;
    sz[u] = 0;
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dfs1(j,u);
        f[u] = (f[u] * f[j] % mod * C(sz[u] + sz[j],sz[j])) % mod;
        sz[u] += sz[j];
    }
    sz[u] ++;//根节点一定是留到最后的所以在求排列组合的时候不考虑进去
}

void dfs2(int u,int father)
{
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        LL fx = (f[u] * qmi(f[j],mod - 2) % mod * qmi(C(n - 1,sz[j]),mod - 2)) % mod;
        f[j] = fx * f[j] % mod * C(n - 1,sz[j] - 1) % mod;
        dfs2(j,u);
    }
    ans = (ans + f[u]) % mod;
}

void solve()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i = 1;i < n;i ++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs1(1,0);
    dfs2(1,0);
    printf("%lld\n",(ans % mod + mod) % mod);
} 

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    init(); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cin >> _;

    // scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

总结：

用树形dp计算拓扑排序的个数
两个序列交叉合并的方案数的计数方式