結果
問題 | No.2531 Coloring Vertices on Namori |
ユーザー |
|
提出日時 | 2023-11-03 23:22:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 1,516 bytes |
コンパイル時間 | 7,263 ms |
コンパイル使用メモリ | 350,048 KB |
実行使用メモリ | 25,216 KB |
最終ジャッジ日時 | 2024-09-25 21:29:06 |
合計ジャッジ時間 | 10,855 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; constexpr int dx[]={1,0,0,-1},dy[]={0,1,-1,0}; constexpr int Dx[]={1,1,0,-1,-1,-1,0,1},Dy[]={0,1,1,1,0,-1,-1,-1}; constexpr int mod=998244353,Mod=1e9+7,inf=Mod; constexpr ll linf=(ll)inf*inf; typedef pair<ll,int>P; #define m_p make_pair struct fastio{ fastio(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }fio; template<class T,class U> bool chmax(T&a,const U&b){ if(a<b){ a=b; return 1; } return 0; } template<class T,class U> bool chmin(T&a,const U&b){ if(a>b){ a=b; return 1; } return 0; } //* #include<atcoder/all> using namespace atcoder; //*/ vector<int>G[200000]; int dep[200000]; int dfs(int v,int p){ if(dep[v]!=-1) return dep[p]-dep[v]+1; if(v==0) dep[v]=0; else dep[v]=dep[p]+1; for(auto x:G[v]){ if(x!=p){ int r=dfs(x,v); if(r!=-1) return r; } } return -1; } ll dp[200000][2]; ll mypow(int x,ll n){ if(n==0) return 1; if(n%2==1) return mypow(x,n-1)*x%mod; ll res=mypow(x,n/2); return res*res%mod; } int main(){ int n,k,u,v; cin>>n>>k; while(cin>>u>>v){ u--,v--; G[u].push_back(v); G[v].push_back(u); } for(int i=0;i<n;i++) dep[i]=-1; int l=dfs(0,-1); dp[0][0]=1; for(int i=1;i<l;i++){ dp[i][0]=dp[i-1][1]; dp[i][1]=(dp[i-1][0]*(k-1)+dp[i-1][1]*(k-2))%mod; } cout<<dp[l-1][1]*k%mod*mypow(k-1,n-l)%mod<<endl; }