BFS

题目大意

给出一个求 $BFS$ 序的方法，求 $BFS$ 序的种类数。

题解思路

问题1：组合排列中的经典计数问题
给定 $a$ 个完全相同的红球与 $b$ 个完全相同的篮球，将它们排成一排，求不同排列情况的总数。这是一个典型的组合问题，可利用组合数公式求解。由于在总共 $a + b$ 个位置中，只需确定 $a$ 个红球的位置（篮球位置随之确定），因此排列情况数为组合数 $\binom{a + b}{a}$。

问题2：树上BFS序的计数问题
对于给定的一棵树，我们的目标是计算从根节点出发，所有可能的广度优先搜索（BFS）序的数目。这里，我们采用树上动态规划的策略来解决。

动态规划过程中，假设当前已处理到节点 $i$，并且已经考虑了其子树的一个特定集合 $S$。其中，集合 $S$ 包含的节点总数为 $x_1$，该集合内所有节点构成的子结构可能产生的BFS序的数量为 $p_1$。此时，若要将一个新的子树纳入考虑范围，该子树的节点数为 $x_2$，其自身可能的BFS序数量为 $p_2$。那么，将新子树加入后形成的新集合 $S_1$，其可能的BFS序数量可通过如下方式计算：

根据分步乘法计数原理，先将原集合 $S$ 的 $p_1$ 种情况与新子树的 $p_2$ 种情况进行组合，得到 $p_1 \times p_2$ 种初步组合。进一步考虑到新子树节点与原集合节点在BFS遍历顺序中的相对位置关系，本质上是在 $x_1 + x_2$ 个位置中选择 $x_1$ 个位置放置原集合节点（剩余位置放置新子树节点），所以最终新集合 $S_1$ 可能的BFS序数量为 $p_1 \times p_2 \times \binom{x_1 + x_2}{x_1}$。通过这样逐步扩展子树集合，自底向上地进行动态规划计算，最终可得到从根节点出发的所有可能BFS序的数目。

问题3：换根DP实现任意节点的BFS序计数
在求解出以1号节点为根时的BFS序情况数后，为了计算以其他节点为根时的情况数，我们引入换根动态规划的方法。

具体操作上，首先针对当前根节点，将其某一棵子树的情况从原有计算结果中去除，消除该子树对当前根节点计算的影响。随后，通过精心设计的状态转移规则，将相关状态信息合理地转移到新选定的根节点上，从而实现从不同节点视角重新计算BFS序的情况数。通过遍历每个节点作为根节点，完成整个换根DP过程，即可得到树中任意节点作为根时可能的BFS序数目。

参考代码

 #include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;

namespace myMath {
    i64 mod = 998244353;

    i64 add(i64 x, i64 y) {
        x += y;
        if (x > mod) x -= mod;
        return x;
    }

    i64 sub(i64 x, i64 y) {
        x -= y;
        if (x < 0)x += mod;
        return x;
    }

    i64 mul(i64 x, i64 y) {
        x *= y;
        x -= x / mod * mod;
        return x;
    }

    i64 qpow(i64 x, i64 y) {
        i64 res = 1;
        while (y) {
            if (y & 1) res = mul(res, x);
            y >>= 1;
            x = mul(x, x);
        }
        return res;
    }

    i64 inv(i64 x) {
        return qpow(x, mod - 2);
    }

    i64 qdiv(i64 x, i64 y) {
        return mul(x, inv(y));
    }

    void set_mod(i64 x) {
        mod = x;
    }

    namespace Comb {
        int n;
        vector<i64> fa;
        vector<i64> ifa;

        void init(int _n) {
            n = _n;
            fa.assign(n + 1, 1), ifa.assign(n + 1, 1);
            for (int i = 1; i <= n; i++) fa[i] = mul(fa[i - 1], i);
            ifa[n] = inv(fa[n]);
            for (i64 i = n - 1; i; i--) {
                ifa[i] = mul(ifa[i + 1], i + 1);
            }
        }

        i64 C(int i, int j) {
            return mul(fa[i], mul(ifa[j], ifa[i - j]));
        }
    }

    //线性求逆元

    vector<i64> get_inv(int k) {
        vector<i64> in(k + 1, 1);
        for (int i = 2; i <= k; i++) {
            in[i] = mul(in[mod % i], sub(mod, mod / i));
        }
        return in;
    }
}

using namespace myMath;
vector<vector<int> > edge ;
vector<i64> ans;
vector<pair<i64, i64> > f;

void dfs1(int fa, int u ) {
    i64 t = 0;
    i64 ff = 1;
    for (auto v: edge[u]) {
        if (v == fa) continue;
        dfs1(u, v);
        auto [s1 , j1] = f[v];

        ff = mul(ff, j1);
        i64 ex = Comb::C(t + s1, s1);
        ff = mul(ff, ex);
        t += s1;
    }
    t++;
    f[u] = {t, ff};
}

void dfs2 (int fa, int u ) {
    auto [aa, bb] = f[u];
    ans[u] = bb;
    for (auto v: edge[u]) {
        if (v == fa)continue;;
        auto t1 = f[u], t2 = f[v];
        auto [x1 ,y1] = t1;
        auto [x2, y2] = t2;
        y1 = qdiv(y1, y2);
        x1--;
        y1 = qdiv(y1, Comb::C(x1, x2));
        x1 -= x2;
        x1++;

        f[u] = {x1, y1};
        y2 = mul(y1, y2);
        x2--;
        x2 += x1;
        y2 = mul(y2, Comb::C(x2, x1));
        x2++;
        f[v] = {x2, y2};
        dfs2(u, v);
        f[u] = t1, f[v] = t2;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    Comb::init(n * 2 + 1000);
    edge.resize(n + 1), ans.resize(n + 1), f.resize(n + 1, {1,1});
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].emplace_back(v);
        edge[v].emplace_back(u);
    }
     
    dfs1(0, 1);
    //
    dfs2(0, 1);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
}