結果
問題 | No.1507 Road Blocked |
ユーザー |
![]() |
提出日時 | 2021-05-14 23:27:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 114 ms / 2,000 ms |
コード長 | 832 bytes |
コンパイル時間 | 2,216 ms |
コンパイル使用メモリ | 196,860 KB |
最終ジャッジ日時 | 2025-01-21 12:21:23 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#define rep(i, n) for (int i = 0; i < (int)(n); i++) #define ALL(v) v.begin(), v.end() typedef long long ll; #include <bits/stdc++.h> using namespace std; vector<int> G[100010]; const ll MOD=998244353; ll modinv(ll a,ll m){ ll b=m,u=1,v=0; while(b){ ll t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); } u%=m; if(u<0) u+=m; return u; } ll A[100010]; ll dfs(int v,int pa){ ll cnt=1; for(auto nv:G[v]){ if(nv==pa) continue; cnt+=dfs(nv,v); } return A[v]=cnt; } int main(){ ll n; cin>>n; rep(i,n-1){ int u,v; cin>>u>>v; u--,v--; G[u].push_back(v); G[v].push_back(u); } dfs(0,-1); ll sum=n*(n-1)/2*(n-1); ll tmp=0; rep(i,n) tmp+=A[i]*(n-A[i]); ll p=sum-tmp,q=sum; ll g=gcd(p,q); p/=g,q/=g; cout<<p%MOD*modinv(q,MOD)%MOD<<endl; return 0; }