結果
問題 | No.1507 Road Blocked |
ユーザー |
|
提出日時 | 2021-05-13 09:45:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 181 ms / 2,000 ms |
コード長 | 1,158 bytes |
コンパイル時間 | 7,156 ms |
コンパイル使用メモリ | 252,320 KB |
最終ジャッジ日時 | 2025-01-21 10:26:54 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> #define rep(i, n) for(int i = 0; i < (int)(n); i++) using mint = atcoder::modint998244353; mint dp[100010]; std::vector<int> G[100010]; bool seen[100010]; int dfs(int node = 0) { for(const auto &to:G[node]) { if(seen[to]) continue; seen[to] = true; dp[node] += dfs(to); } return (++dp[node]).val(); } int main() { long long n; std::cin >> n; std::vector<std::pair<long long, long long>> v(n-1); rep(i, n-1) { int a, b; std::cin >> a >> b; a--, b--; v[i] = {a, b}; G[a].push_back(b); G[b].push_back(a); } seen[0] = true; dfs(); //rep(i, n) std::cout << dp[i].val() << ' ';std::endl(std::cout); mint ans = 0; for(auto [a, b]:v) { if(dp[a].val()<dp[b].val()) std::swap(a, b); ans += (n-dp[b])*dp[b]; //std::cout << (dp[a]-dp[b]).val() << ' ' << dp[b].val() << std::endl; } //rep(i, n) ans += dp[i]*(n-dp[i]); //std::cout << ans.val() << std::endl; ans/=(n-1)*n*(n-1)/2; ans = 1-ans; std::cout << ans.val() << std::endl; return 0; }