結果
問題 | No.2504 NOT Path Painting |
ユーザー |
![]() |
提出日時 | 2023-08-03 12:40:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 231 ms / 2,000 ms |
コード長 | 2,159 bytes |
コンパイル時間 | 1,268 ms |
コンパイル使用メモリ | 98,160 KB |
実行使用メモリ | 8,616 KB |
最終ジャッジ日時 | 2024-09-15 14:04:46 |
合計ジャッジ時間 | 6,615 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <cassert> #include <iostream> #include <vector> #include <atcoder/modint> using mint = atcoder::modint998244353; int ChoosePair(const int n) { return n * (n + 1) / 2; } mint Solve(const std::vector<std::vector<int>>& tree) { const int n = tree.size(); const mint denominator = mint(ChoosePair(n)).inv(); const auto F = [](const mint& probability) -> mint { return probability * (2 - probability) * (1 - probability).pow(2).inv(); }; std::vector<int> parent(n, -1); std::vector<int> subtree(n, 1); // 根を頂点 1 とする部分木の大きさ const auto CalcSubtree = [&tree, &parent, &subtree]( auto CalcSubtree, const int vertex) -> void { for (const int neighborhood : tree[vertex]) { if (neighborhood != parent[vertex]) { parent[neighborhood] = vertex; CalcSubtree(CalcSubtree, neighborhood); subtree[vertex] += subtree[neighborhood]; } } }; CalcSubtree(CalcSubtree, 0); mint ans = 0; // 長さ 0 のパス for (int i = 0; i < n; ++i) { int num_of_path = 0; for (const int neighborhood : tree[i]) { num_of_path += ChoosePair(neighborhood == parent[i] ? n - subtree[i] : subtree[neighborhood]); } ans += F(1 - num_of_path * denominator) * num_of_path * denominator; } // 長さ 1 のパス for (int i = 0; i < n; ++i) { for (const int j : tree[i]) { if (j == parent[i]) continue; ans += F((n - subtree[j]) * subtree[j] * denominator) * (-ChoosePair(n - subtree[j]) - ChoosePair(subtree[j])) * denominator; } } return ans; } int main() { constexpr int kMaxT = 100000, kMaxN = 40000; int t; std::cin >> t; assert(1 <= t && t <= kMaxT); while (t--) { int n; std::cin >> n; assert(2 <= n && n <= kMaxN); std::vector<std::vector<int>> tree(n); for (int i = 0; i < n - 1; ++i) { int u, v; std::cin >> u >> v; assert(1 <= u && u <= n && 1 <= v && v <= n); --u; --v; tree[u].emplace_back(v); tree[v].emplace_back(u); } std::cout << Solve(tree).val() << '\n'; } return 0; }