結果
問題 | 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;}