Code : Count Spanning Subgraphs

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

class Tree {
  public:
    int n;
    vector<vector<int>> adj;
    vector<vector<mint>> dp;
    // dp[i][d] represents the number of configurations of the i-th subtree
    // in which the i-th node has degree d.
    Tree(int n) {
        this->n = n;
        adj.resize(n);
        dp.resize(n, vector<mint>(n + 1, 0));
    }

    void dfs(int src, int par) {
        dp[src][0] = 1;
        for (auto child : adj[src]) {
            if (child == par) {
                continue;
            }
            dfs(child, src);
            vector<mint> ndp(n + 1);
            for (int d = 0; d < adj[src].size(); d++) {
                for (int now = 0; now < adj[child].size(); now++) {
                    ndp[d] += dp[src][d] * dp[child][now];
                    ndp[d + 1] += dp[src][d] * dp[child][now];
                }
            }
            swap(dp[src], ndp);
        }
    }
};

void solve() {
    int n;
    cin >> n;
    Tree t(n);

    int m = n - 1;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        t.adj[x].push_back(y);
        t.adj[y].push_back(x);
    }

    t.dfs(0, -1);
    mint ans = 0;
    for (int d = 0; d < n; d++) {
        mint current = t.dp[0][d];
        cout << current.val() << " ";
        ans += current;
    }
    cout << "\n";
    cout << ans.val() << "\n";
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

class Tree {
  public:
    int n;
    vector<vector<int>> adj;
    vector<int> deg;
    vector<vector<mint>> dp;
    // dp[i][d] represents the number of configurations of the i-th subtree
    // in which the i-th node has degree d.
    vector<mint> cnt, fac;
    // cnt[i] represents the number of configurations of the i-th subtree.
    Tree(int n) {
        this->n = n;
        adj.resize(n);
        deg.resize(n);
        dp.resize(n, vector<mint>(n, 0));
        cnt.resize(n);

        fac.resize(n + 2);
        fac[0] = 1;
        for (int i = 1; i < n + 2; i++) {
            fac[i] = i * fac[i - 1];
        }
    }

    mint choose(int n, int r) {
        if (n < r) {
            return 0;
        }
        return fac[n] / (fac[r] * fac[n - r]);
    }

    void dfs(int src, int par) {
        deg[src] = adj[src].size();
        mint ways_prod = 1;
        int c = 0;
        for (auto child : adj[src]) {
            if (child != par) {
                dfs(child, src);
                c++;
                ways_prod *= cnt[child];
            }
        }

        for (int d = 0; d <= deg[src]; d++) {
            dp[src][d] = choose(c, d) * ways_prod;
        }

        for (int d = 0; d <= deg[src]; d++) {
            cnt[src] += dp[src][d];
        }
    }
};

void solve() {
    int n;
    cin >> n;
    Tree t(n);

    int m = n - 1;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        t.adj[x].push_back(y);
        t.adj[y].push_back(x);
    }

    t.dfs(0, -1);
    cout << t.cnt[0].val() << endl;
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}