結果
問題 | 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_pairstruct 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;elsedep[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;}