結果
問題 | 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;}