結果
問題 | No.1507 Road Blocked |
ユーザー |
![]() |
提出日時 | 2022-01-13 04:21:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 1,190 bytes |
コンパイル時間 | 889 ms |
コンパイル使用メモリ | 74,368 KB |
実行使用メモリ | 14,208 KB |
最終ジャッジ日時 | 2024-11-15 23:16:54 |
合計ジャッジ時間 | 5,142 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream>#include <vector>using namespace std;using ll = long long;using P = pair<int, int>;using graph = vector<vector<int>>;constexpr ll MOD = 998244353;graph G;vector<ll> cnt;ll modpow(ll a, ll x){ll ans = 1;while(x > 0){if(x & 1){ans *= a;ans %= MOD;}a *= a;a %= MOD;x >>= 1;}return ans;}int dfs(int c, int p){// cout << c << " ";if(cnt[c] != -1) return cnt[c];cnt[c] = 1;for(auto &nex: G[c]){if(nex == p) continue;cnt[c] += dfs(nex, c);}return cnt[c];}int main(){ll n;cin >> n;G = graph(n);cnt = vector<ll>(n, -1);//parent = vector<int>(n, -1);for(int i = 0; i < n-1; i++){int u, v;cin >> u >> v;u--; v--;G[u].push_back(v);G[v].push_back(u);}// cerr << " ";dfs(0, -1);ll tot = 0;for(int i = 1; i < n; i++){tot += (n-cnt[i])*(n-cnt[i]-1);tot += cnt[i]*(cnt[i]-1);// cout << tot << " ";tot %= MOD;}cout << tot*modpow(n*(n-1)%MOD*(n-1)%MOD, MOD-2)%MOD << endl;return 0;}