제출 #498030

#제출 시각아이디문제언어결과실행 시간메모리
498030andrei_boacaStar Trek (CEOI20_startrek)C++17
100 / 100
138 ms32112 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; ll n,d,nr[2][2],nrL,nrW,dp[100005][2][2],win[100005],rez[2][2],c[2][2],sol[2][2],parent[100005],nrlose[100005]; ll suma[100005][2][2]; vector<int> muchii[100005]; set<int> losers[100005]; bool use[100005]; void mult(ll a[2][2],ll b[2][2]) { for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) { c[i][j]=0; for(int k=0;k<=1;k++) c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%mod)%mod; } } void matpw(ll b) { while(b) { if(b&1) { mult(rez,nr); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) rez[i][j]=c[i][j]; } b/=2; mult(nr,nr); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) nr[i][j]=c[i][j]; } } void dfs(int nod,int par) { parent[nod]=par; nrlose[nod]=0; win[nod]=0; for(int i:muchii[nod]) if(i!=par) { dfs(i,nod); if(win[i]==0) { losers[nod].insert(i); nrlose[nod]++; win[nod]=1; } } for(int i:muchii[nod]) if(i!=par) { for(int j=0;j<=1;j++) for(int k=0;k<=1;k++) suma[nod][j][k]=(suma[nod][j][k]+dp[i][j][k])%mod; if(win[i]==0) nrlose[nod]--; if(nrlose[nod]==0) { dp[nod][0][1]=(dp[nod][0][1]+dp[i][1][1])%mod; dp[nod][0][0]=(dp[nod][0][0]+dp[i][1][0])%mod; } else { dp[nod][1][1]=(dp[nod][1][1]+dp[i][1][1])%mod; dp[nod][1][0]=(dp[nod][1][0]+dp[i][1][0])%mod; } dp[nod][1][1]=(dp[nod][1][1]+dp[i][0][1])%mod; dp[nod][1][0]=(dp[nod][1][0]+dp[i][0][0])%mod; if(win[i]==0) nrlose[nod]++; } if(nrlose[nod]==0) { dp[nod][1][0]++; dp[nod][1][0]%=mod; dp[nod][0][1]++; dp[nod][0][1]%=mod; } else { dp[nod][1][0]++; dp[nod][1][0]%=mod; dp[nod][1][1]++; dp[nod][1][1]%=mod; } } void recalc(int nod) { for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) dp[nod][i][j]=0; if(nrlose[nod]>0) win[nod]=1; else win[nod]=0; if(nrlose[nod]>1) { dp[nod][1][1]=(suma[nod][1][1]+suma[nod][0][1])%mod; dp[nod][1][0]=(suma[nod][1][0]+suma[nod][0][0])%mod; } if(nrlose[nod]==1) { int lose=*losers[nod].begin(); dp[nod][1][1]=(suma[nod][1][1]+suma[nod][0][1])%mod; dp[nod][1][1]-=dp[lose][1][1]; if(dp[nod][1][1]<0) dp[nod][1][1]+=mod; dp[nod][1][0]=(suma[nod][1][0]+suma[nod][0][0])%mod; dp[nod][1][0]-=dp[lose][1][0]; if(dp[nod][1][0]<0) dp[nod][1][0]+=mod; dp[nod][0][1]=dp[lose][1][1]; dp[nod][0][0]=dp[lose][1][0]; } if(nrlose[nod]==0) { dp[nod][0][0]=suma[nod][1][0]; dp[nod][0][1]=suma[nod][1][1]; dp[nod][1][0]=suma[nod][0][0]; dp[nod][1][1]=suma[nod][0][1]; } if(nrlose[nod]==0) { dp[nod][1][0]++; dp[nod][1][0]%=mod; dp[nod][0][1]++; dp[nod][0][1]%=mod; } else { dp[nod][1][0]++; dp[nod][1][0]%=mod; dp[nod][1][1]++; dp[nod][1][1]%=mod; } } void reroot(int par,int fiu) { if(win[fiu]==0) { nrlose[par]--; losers[par].erase(fiu); } for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) { suma[par][i][j]-=dp[fiu][i][j]; if(suma[par][i][j]<0) suma[par][i][j]+=mod; } recalc(par); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) { suma[fiu][i][j]+=dp[par][i][j]; if(suma[fiu][i][j]>=mod) suma[fiu][i][j]-=mod; } if(win[par]==0) { nrlose[fiu]++; losers[fiu].insert(par); } recalc(fiu); } void calcdp(int nod) { use[nod]=1; for(int i:muchii[nod]) if(!use[i]) { reroot(nod,i); int root=i; for(int k=0;k<=1;k++) for(int j=0;j<=1;j++) { nr[j][k]=(nr[j][k]+dp[root][k][j]); if(nr[j][k]>=mod) nr[j][k]-=mod; } if(win[root]==0) nrL++; if(win[root]==1) nrW++; calcdp(i); reroot(i,nod); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>d; for(int i=1;i<n;i++) { int a,b; cin>>a>>b; muchii[a].push_back(b); muchii[b].push_back(a); } for(int root=1;root<=1;root++) { for(int i=1;i<=n;i++) { win[i]=0; for(int j=0;j<=1;j++) for(int k=0;k<=1;k++) dp[i][j][k]=0; } dfs(root,0); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) { nr[j][i]=(nr[j][i]+dp[root][i][j]); if(nr[j][i]>=mod) nr[j][i]-=mod; } if(win[root]==0) nrL++; if(win[root]==1) nrW++; if(root==1) { for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) sol[i][j]=dp[root][i][j]; } } calcdp(1); rez[0][0]=nrL; rez[0][1]=nrW; if(d>1) matpw(d-1); ll ans=(sol[1][0]*rez[0][0])%mod; ans=(ans+sol[1][1]*rez[0][1]%mod)%mod; cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...