結果
問題 | No.2504 NOT Path Painting |
ユーザー |
|
提出日時 | 2023-10-13 22:44:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 138 ms / 2,000 ms |
コード長 | 942 bytes |
コンパイル時間 | 837 ms |
コンパイル使用メモリ | 77,756 KB |
実行使用メモリ | 9,312 KB |
最終ジャッジ日時 | 2024-09-15 18:29:59 |
合計ジャッジ時間 | 3,955 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cassert>#include<atcoder/modint>using namespace std;using mint=atcoder::modint998244353;int N;vector<int>G[40000];int ch[40000];void dfs1(int u,int p){ch[u]=1;for(int v:G[u])if(v!=p){dfs1(v,u);ch[u]+=ch[v];}}mint ans;mint ALL_INV;void dfs2(int u,int p,int pc){mint P,Q;{mint sum=pc;mint cur=N;for(int v:G[u])if(v!=p){cur+=sum*ch[v];sum+=ch[v];}P=cur*ALL_INV;Q=mint(pc)*ch[u]*ALL_INV;}ans+=P/(1-P);ans-=Q/(1-Q);for(int v:G[u])if(v!=p)dfs2(v,u,N-ch[v]);}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;for(;T--;){cin>>N;for(int i=0;i<N;i++)G[i].clear();for(int i=1;i<N;i++){int u,v;cin>>u>>v;u--,v--;G[u].push_back(v);G[v].push_back(u);}dfs1(0,-1);ans=1;ALL_INV=mint((long)N*(N+1)/2).inv();dfs2(0,-1,0);cout<<ans.val()<<"\n";}}