結果

問題 No.2504 NOT Path Painting
ユーザー suisensuisen
提出日時 2023-07-22 17:01:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 150 ms / 2,000 ms
コード長 1,559 bytes
コンパイル時間 851 ms
コンパイル使用メモリ 79,800 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2023-10-13 18:14:51
合計ジャッジ時間 6,267 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 94 ms
4,352 KB
testcase_02 AC 94 ms
4,352 KB
testcase_03 AC 94 ms
4,348 KB
testcase_04 AC 95 ms
4,348 KB
testcase_05 AC 95 ms
4,372 KB
testcase_06 AC 93 ms
4,352 KB
testcase_07 AC 94 ms
4,348 KB
testcase_08 AC 94 ms
4,352 KB
testcase_09 AC 94 ms
4,352 KB
testcase_10 AC 93 ms
4,352 KB
testcase_11 AC 94 ms
4,352 KB
testcase_12 AC 95 ms
4,348 KB
testcase_13 AC 115 ms
4,356 KB
testcase_14 AC 116 ms
4,372 KB
testcase_15 AC 135 ms
5,808 KB
testcase_16 AC 146 ms
5,556 KB
testcase_17 AC 142 ms
5,508 KB
testcase_18 AC 123 ms
5,820 KB
testcase_19 AC 150 ms
10,136 KB
testcase_20 AC 128 ms
10,752 KB
権限があれば一括ダウンロードができます

ソースコード

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