Submission #38492131

---

Source Code Expand

/*
 * File created on 01/30/2023 at 18:37:19.
 * Link to problem: 
 * Description: 
 * Time complexity: O()
 * Space complexity: O()
 * Status: ---
 * Copyright: Ⓒ 2023 Francois Vogel
*/

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pii pair<int, int>
#define f first
#define s second

#define vi vector<int>
#define all(x) x.begin(), x.end()
#define sz(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear

#define int ll
#define ll long long
#define ld long double

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int siz = 5040;
const int MOD = 998244353;

vi graph [siz];

vector<vi> dfs(int x, int p = -1) {
    vector<vi> dp = {{1, 0}, {0, 1}};
    for (int y : graph[x]) if (y != p) {
        auto ret = dfs(y, x);
        vector<vi> ndp = vector<vi>(2, vi(sz(dp[0])+sz(ret[0])-1, 0));
        for (int j = 0; j < sz(dp[0]); j++) {
            for (int k = 0; k < sz(ret[0]); k++) {
                ndp[0][j+k] += dp[0][j]*(ret[0][k]+ret[1][k])%MOD;
                ndp[0][j+k] %= MOD;
                ndp[1][j+k] += dp[1][j]*ret[0][k]%MOD;
                ndp[1][j+k] %= MOD;
                if (j+k > 0) {
                    ndp[1][j+k-1] += dp[1][j]*ret[1][k]%MOD;
                    ndp[1][j+k-1] %= MOD;
                }
            }
        }
        swap(dp, ndp);
    }
    return dp;
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        graph[x].pb(y);
        graph[y].pb(x);
    }
    vector<vi> dp = dfs(0);
    for (int i = 1; i <= n; i++) {
        cout << (dp[0][i]+dp[1][i])%MOD << "\n";
    }

    cout.flush();
    int d = 0;
    d++;
}

Submission Info

Judge Result