結果
問題 | No.1507 Road Blocked |
ユーザー |
|
提出日時 | 2021-05-14 22:23:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 105 ms / 2,000 ms |
コード長 | 637 bytes |
コンパイル時間 | 2,053 ms |
コンパイル使用メモリ | 195,632 KB |
最終ジャッジ日時 | 2025-01-21 11:30:01 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>#define int long longusing namespace std;constexpr int mod=998244353;int N,ans;vector<int>G[100010];int dfs(int v,int p){int sum=1;for(int t:G[v]) if(t!=p){sum+=dfs(t,v);}(ans+=sum*(N-sum))%=mod;return sum;}int mod_pow(int a,int b){if(!b)return 1;if(b&1)return mod_pow(a,b-1)*a%mod;int c=mod_pow(a,b/2);return c*c%mod;}signed main(){cin>>N;for(int i=0;i<N-1;i++){int a,b; cin>>a>>b;G[--a].push_back(--b);G[b].push_back(a);}dfs(0,-1);cout<<(1+mod-ans*mod_pow(N*(N-1)/2%mod*(N-1)%mod,mod-2)%mod)%mod<<endl;}