結果

問題 No.2504 NOT Path Painting
ユーザー 👑 emthrmemthrm
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0