結果

問題 No.3449 Mex of Subtree
コンテスト
ユーザー otoshigo
提出日時 2026-02-21 16:27:51
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 204 ms / 2,000 ms
コード長 1,944 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,727 ms
コンパイル使用メモリ 347,560 KB
実行使用メモリ 49,664 KB
最終ジャッジ日時 2026-02-21 16:28:02
合計ジャッジ時間 9,867 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1 << 30;
const ll INF = 1LL << 60;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
#define rep(i, s, t) for (ll i = (ll)s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

template <class T1, class T2>
bool chmin(T1& x, T2 y) { return x > y ? (x = y, true) : false; }
template <class T1, class T2>
bool chmax(T1& x, T2 y) { return x < y ? (x = y, true) : false; }

template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_heap = priority_queue<T>;

#include <atcoder/modint>
using mint = atcoder::modint998244353;

void solve() {
    int N;
    cin >> N;
    vector<vector<int>> G(N);
    vector<int> P(N, -1);
    rep(i, 1, N) {
        int p;
        cin >> p;
        p--;
        P[i] = p;
        G[i].push_back(p);
        G[p].push_back(i);
    }
    vector<vector<mint>> dp(N);
    vector<int> D(N);
    auto dfs = [&](auto dfs, int x, int p) -> void {
        D[x] = 1;
        dp[x].resize(D[x] + 1);
        dp[x][1] = 1;
        for (auto i : G[x]) {
            if (i == p) continue;
            dfs(dfs, i, x);
            vector<mint> nxt(D[x] + D[i] + 1);
            rep(k, 0, D[x] + 1) rep(l, 0, D[i] + 1) {
                nxt[k] += dp[x][k] * dp[i][l];
                if (k + l + 1 <= D[x] + D[i]) nxt[k + l + 1] -= dp[x][k] * dp[i][l];
            }
            rep(k, 0, D[x] + D[i]) nxt[k + 1] += nxt[k];
            D[x] += D[i];
            swap(dp[x], nxt);
        }
    };
    dfs(dfs, 0, -1);
    mint ans = 0;
    rep(i, 0, N + 1) ans += (i + 1) * dp[0][i];
    cout << ans.val() << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(15);
    srand(time(NULL));

    int T;
    // cin >> T;
    T = 1;
    while (T--) solve();
}
0