結果
問題 | No.2504 NOT Path Painting |
ユーザー |
👑 ![]() |
提出日時 | 2023-08-02 16:55:31 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,128 bytes |
コンパイル時間 | 1,380 ms |
コンパイル使用メモリ | 101,072 KB |
実行使用メモリ | 21,288 KB |
最終ジャッジ日時 | 2024-11-20 06:53:31 |
合計ジャッジ時間 | 35,180 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 13 TLE * 8 |
ソースコード
#include <cassert>#include <iostream>#include <vector>#include <atcoder/modint>using mint = atcoder::modint998244353;int ChoosePair(const int n) { return n * (n + 1) / 2; }// <TLE>// Õ(n^3) 時間?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();};const auto G = [&denominator, F](const int num1, const int num2) -> mint {return F(num1 * num2 * denominator);};std::vector<int> subtree(n); // 部分木の大きさconst auto CalcSubtree = [&tree, &subtree](auto CalcSubtree, const int parent, const int vertex) -> void {subtree[vertex] = 1;for (const int neighborhood : tree[vertex]) {if (neighborhood != parent) {CalcSubtree(CalcSubtree, vertex, neighborhood);subtree[vertex] += subtree[neighborhood];}}};// 最後の操作前にそのパスが白く塗られている期待値を求めるmint ans = 0;const auto dfs = [&tree, n, &denominator, G, &subtree, &ans](auto dfs, const int root, const int child_of_root,const int parent, const int vertex, const int distance, int bad_choice)-> void {for (const int neighborhood_of_vertex : tree[vertex]) {if (neighborhood_of_vertex != parent) {bad_choice += ChoosePair(subtree[neighborhood_of_vertex]);}}if (distance < n - 1 && root < vertex) {mint expected_value = G(n - subtree[child_of_root], subtree[vertex]);for (const int neighborhood_of_root : tree[root]) {if (neighborhood_of_root != child_of_root) {expected_value -= G(subtree[neighborhood_of_root], subtree[vertex]);}}for (const int neighborhood_of_vertex : tree[vertex]) {if (neighborhood_of_vertex != parent) {expected_value -=G(n - subtree[child_of_root], subtree[neighborhood_of_vertex]);}}for (const int neighborhood_of_root : tree[root]) {if (neighborhood_of_root == child_of_root) continue;for (const int neighborhood_of_vertex : tree[vertex]) {if (neighborhood_of_vertex == parent) continue;expected_value +=G(subtree[neighborhood_of_root], subtree[neighborhood_of_vertex]);}}ans += expected_value * bad_choice * denominator;}for (const int neighborhood : tree[vertex]) {if (neighborhood != parent) {dfs(dfs, root, child_of_root, vertex, neighborhood,distance + 1, bad_choice - ChoosePair(subtree[neighborhood]));}}};for (int root = 0; root < n; ++root) {CalcSubtree(CalcSubtree, -1, root);int bad_choice = 0;for (const int child : tree[root]) bad_choice += ChoosePair(subtree[child]);for (const int child : tree[root]) {dfs(dfs, root, child, root,child, 1, bad_choice - ChoosePair(subtree[child]));}// パス P = (root) のときmint expected_value = F(1 - bad_choice * denominator);for (const int child : tree[root]) {expected_value -= G(n - subtree[child], subtree[child]);}const int children_num = tree[root].size();for (int i = 0; i < children_num; ++i) {for (int j = i + 1; j < children_num; ++j) {expected_value += G(subtree[tree[root][i]], subtree[tree[root][j]]);}}ans += expected_value * bad_choice * 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;}