結果
問題 | No.1507 Road Blocked |
ユーザー |
![]() |
提出日時 | 2021-05-14 22:33:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 121 ms / 2,000 ms |
コード長 | 739 bytes |
コンパイル時間 | 4,410 ms |
コンパイル使用メモリ | 252,500 KB |
最終ジャッジ日時 | 2025-01-21 11:39:10 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include "atcoder/all" using namespace atcoder; using Mint = modint998244353; int N; vector<vector<int>> G; Mint ans = 0; int maine(int now = 0, int par = -1) { int ret = 1; for (auto&& nxt : G[now]) { if (par == nxt) continue; ret += maine(nxt, now); } if (par != -1) ans += Mint{ret} * (ret - 1) + Mint{N - ret} * (N - ret - 1); return ret; } int main() { cin >> N; G.resize(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--; v--; G[u].emplace_back(v); G[v].emplace_back(u); } maine(); cout << (ans / N / (N - 1) / (N - 1)).val() << endl; }