Code : Induced Subgraphs with Compressed Degree

#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] is the count of induced connected subgraph such that the highest
    // vertex is node i and it has degree d.
    // All degrees >= 2 are treated as identical.
    Tree(int n) {
        this->n = n;
        adj.resize(n);
        dp.resize(n, vector<mint>(3, 0));
    }

    void dfs(int src, int par) {
        // Start with no children.
        dp[src][0] = 1;
        for (auto child : adj[src]) {
            if (child == par) {
                continue;
            }
            dfs(child, src);
            vector<mint> ndp(3);
            for (int d = 0; d < 3; d++) {
                // Ignore this children.
                ndp[d] += dp[src][d];
                for (int now = 0; now < 3; now++) {
                    int nxt = d + 1;
                    if (nxt > 1) {
                        nxt = 2;
                    }
                    // Append this children.
                    ndp[nxt] += 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;
    auto &dp = t.dp;
    for (int i = 0; i < n; i++) {
        for (int d = 0; d < 3; d++) {
            if (i == 0) {
                cout << dp[i][d].val() << " ";
            }
            ans += dp[i][d];
        }
    }
    cout << endl;
    cout << ans.val() << endl;
}

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