結果

問題 No.2504 NOT Path Painting
ユーザー suisen
提出日時 2023-07-22 17:01:53
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 1,559 bytes
コンパイル時間 2,146 ms
コンパイル使用メモリ 104,436 KB
最終ジャッジ日時 2025-02-15 18:02:47
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

#include <atcoder/modint>

using mint = atcoder::modint998244353;

using Vertex = uint32_t;
using Graph = std::vector<std::vector<Vertex>>;

mint solve(const uint32_t n, const Graph &g) {
    const mint m = n * (n + 1) / 2;

    static constexpr Vertex absent = ~Vertex(0);

    mint ans = 0;
    auto dfs = [&](auto dfs, const Vertex u, const Vertex p) -> uint32_t {
        // # of paths including {u}
        mint p_u = m;

        // size of subtree u
        uint32_t subu = 1;
        for (Vertex v : g[u]) if (v != p) {
            // size of subtree v
            uint32_t subv = dfs(dfs, v, u);

            p_u -= subv * (subv + 1) / 2;

            // # of paths including {u, v}
            mint p_uv = subv * (n - subv);
            ans -= m / (m - p_uv);

            subu += subv;
        }
        if (p != absent) {
            uint32_t subp = n - subu;
            p_u -= subp * (subp + 1) / 2;
        }
        ans += m / (m - p_u);
        return subu;
    };
    dfs(dfs, 0, absent);
    
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    uint32_t t;
    std::cin >> t;

    for (uint32_t case_id = 0; case_id < t; ++case_id) {
        uint32_t n;
        std::cin >> n;

        Graph g(n);
        for (uint32_t i = 0; i < n - 1; ++i) {
            Vertex u, v;
            std::cin >> u >> v;
            --u, --v;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        std::cout << solve(n, g).val() << '\n';
    }
}
0