結果
問題 | No.2504 NOT Path Painting |
ユーザー |
|
提出日時 | 2023-03-30 16:00:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,362 bytes |
コンパイル時間 | 2,605 ms |
コンパイル使用メモリ | 77,688 KB |
最終ジャッジ日時 | 2025-02-11 19:10:15 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | RE * 8 MLE * 13 |
ソースコード
#include <iostream>#include <vector>#include <atcoder/modint>using mint = atcoder::modint998244353;namespace atcoder {std::istream& operator>>(std::istream& in, mint &a) {long long e; in >> e; a = e;return in;}std::ostream& operator<<(std::ostream& out, const mint &a) {out << a.val();return out;}} // namespace atcoderint main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin >> n;std::vector<std::vector<int>> g(n);for (int i = 0; i < n - 1; ++i) {int u, v;std::cin >> u >> v;--u, --v;g[u].push_back(v);g[v].push_back(u);}const mint m = n * (n + 1) / 2;mint ans = 1;auto dfs = [&](auto dfs, int u, int p) -> long long {mint P_u = m;long long subu = 1;for (int v : g[u]) if (v != p) {long long subv = dfs(dfs, v, u);P_u -= subv * (subv + 1) / 2;mint P_uv = mint(subv) * (n - subv);ans -= P_uv / (m - P_uv);subu += subv;}if (p != -1) {long long subp = n - subu;P_u -= subp * (subp + 1) / 2;}ans += P_u / (m - P_u);return subu;};dfs(dfs, 0, -1);std::cout << ans.val() << std::endl;}