提出 #69711324

---

ソースコード 拡げる

// authored by GPT-5 pro
#include <bits/stdc++.h>
using namespace std;

static const int MOD = 998244353;

long long modpow(long long a, long long e) {
    long long r = 1 % MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if (!(cin >> N)) return 0;
    vector<vector<int>> g(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b; cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // Precompute modular inverses up to 2N+2 (for 1/(2(k+1)))
    int LIM = 2 * N + 5;
    vector<int> inv(LIM);
    inv[1] = 1;
    for (int i = 2; i < LIM; ++i) {
        inv[i] = (long long)(MOD - MOD / i) * inv[MOD % i] % MOD;
    }

    // Convolution (naive) for polynomials in x^2
    auto mul = [&](const vector<int>& A, const vector<int>& B) -> vector<int> {
        vector<int> C(A.size() + B.size() - 1, 0);
        for (size_t i = 0; i < A.size(); ++i) {
            long long ai = A[i];
            for (size_t j = 0; j < B.size(); ++j) {
                C[i + j] = (C[i + j] + (ai * B[j]) % MOD) % MOD;
            }
        }
        return C;
    };

    vector<int> parent(N, -1);
    // Root the tree at 0
    {
        // simple BFS to set parent (optional; we’ll still DFS below)
        queue<int> q;
        q.push(0);
        parent[0] = 0;
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int to : g[v]) if (parent[to] == -1) {
                parent[to] = v;
                q.push(to);
            }
        }
        parent[0] = -1;
    }

    // DFS returning (F_v polynomial, C_v)
    function<pair<vector<int>, int>(int,int)> dfs = [&](int v, int p) -> pair<vector<int>, int> {
        vector<vector<int>> childPolys;
        childPolys.reserve(g[v].size());
        for (int to : g[v]) if (to != p) {
            auto pr = dfs(to, v);
            childPolys.push_back(move(pr.first));
        }

        // Multiply child polynomials: Q_v(x) = prod F_child(x)
        sort(childPolys.begin(), childPolys.end(),
             [](const vector<int>& A, const vector<int>& B) { return A.size() < B.size(); });
        vector<int> Q(1, 1); // constant 1
        for (auto &P : childPolys) {
            Q = mul(Q, P);
        }

        // C_v = sum_{k} Q[k] / (2*(k+1))
        int C = 0;
        for (size_t k = 0; k < Q.size(); ++k) {
            int denom = 2 * (int(k) + 1);
            int term = (long long)Q[k] * inv[denom] % MOD;
            C += term; if (C >= MOD) C -= MOD;
        }

        // F_v(x) = C_v + x^2 * Q_v(x)  ==> coefficients in x^{2j}
        vector<int> F; F.resize(Q.size() + 1);
        F[0] = C;
        for (size_t j = 0; j < Q.size(); ++j) F[j + 1] = Q[j];

        return { move(F), C };
    };

    auto rootRes = dfs(0, -1);
    int C_root = rootRes.second; // integral at root

    // Multiply by (1/N)^N
    long long invN = modpow(N % MOD, MOD - 2);
    long long scale = modpow(invN, N);
    long long ans = (long long)C_root * scale % MOD;

    cout << ans << '\n';
    return 0;
}

提出情報

ジャッジ結果