#include<bits/stdc++.h>
using namespace std;
long long mod=1e9+7;
long long mypow(long long m,long long y){
if(y==0){
return 1;
}
long long p=mypow(m,(y>>1));
p*=p;
p%=mod;
if(y&1){
p*=m;
p%=mod;
}
return p;
}
long long n,d;
const long long maxn=1000+10;
vector<long long>adj[maxn];
long long cnttagh,cntnafaraval,cntnafardovom,dp[maxn],tagh[maxn];
vector<vector<long long>>mat(2,vector<long long>(2)),mata(2,vector<long long>(1)),res;
void zarb(vector<vector<long long>>a,vector<vector<long long>>b){
long long n1=a.size(),m1=a.back().size(),n2=b.size(),m2=b.back().size();
res.clear();
if(m1!=n2){
return ;
}
res.resize(n1,vector<long long>(m2));
for(long long i=0;i<n1;i++){
for(long long j=0;j<m2;j++){
for(long long h=0;h<m1;h++){
res[i][j]+=a[i][h]*b[h][j];
res[i][j]%=mod;
}
}
}
}
void tav(vector<vector<long long>>&a,long long b){
vector<vector<long long>>fake=a;
b--;
while(b>0){
if(b&1){
zarb(fake,a);
a=res;
}
zarb(fake,fake);
fake=res;
b>>=1;
}
}
void aval(long long u,long long para=0){
for(auto x:adj[u]){
if(x!=para){
aval(x,u);
if(dp[x]==0){
dp[u]++;
}
}
}
}
void caltagh(long long u,long long para=0){
if(para==0){
tagh[u]=1;
}
else if(tagh[para]==1){
if(dp[para]==0){
tagh[u]=1;
}
else if(dp[para]==1&&dp[u]==0){
tagh[u]=1;
}
}
if(tagh[u]==1&&dp[u]==0){
cnttagh++;
}
for(auto x:adj[u]){
if(x==para){
continue;
}
caltagh(x,u);
}
}
void caldp(long long u,long long para=0,long long cn=1){
if(cn==0){
dp[u]++;
}
if(dp[u]==0){
if(u<=n)
cntnafardovom++;
}
else{
if(u<=n)
cntnafaraval++;
}
for(auto x:adj[u]){
if(x!=para){
if(dp[x]==0){
caldp(x,u,dp[u]-1);
}
else{
caldp(x,u,dp[u]);
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>d;
for(long long i=0;i<n-1;i++){
long long u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
aval(1);
caltagh(1);
caldp(1);
long long z=dp[1];
mata[0][0]=cntnafaraval;
mata[1][0]=cntnafardovom;
mat[0][0]=cntnafaraval*n;
mat[1][0]=cntnafardovom*n;
if(d==1){
long long res=0;
if(dp[1]>=1){
res=1ll*(n-cnttagh)*n%mod;
res+=1ll*cnttagh*cntnafaraval%mod;
res%=mod;
cout<<res<<"\n";
}
else{
res=1ll*cnttagh*cntnafardovom%mod;
cout<<res<<"\n";
}
return 0;
}
mat[0][1]=sumnafaval;
mat[1][1]=sumnafdovom;
cntnafaraval=0;
cntnafardovom=0;
tav(mat,d-1);
zarb(mat,mata);
cntnafaraval=res[0][0];
cntnafardovom=res[1][0];
long long sm=cntnafaraval+cntnafardovom;
long long res=0;
if(z>=1){
res=1ll*(n-cnttagh)*(sm)%mod;
res+=1ll*cnttagh*cntnafaraval%mod;
res%=mod;
cout<<res<<"\n";
}
else{
res=1ll*cnttagh*cntnafardovom%mod;
cout<<res<<"\n";
}
return 0;
}
Compilation message
startrek.cpp: In function 'int main()':
startrek.cpp:145:12: error: 'sumnafaval' was not declared in this scope
145 | mat[0][1]=sumnafaval;
| ^~~~~~~~~~
startrek.cpp:146:12: error: 'sumnafdovom' was not declared in this scope; did you mean 'cntnafardovom'?
146 | mat[1][1]=sumnafdovom;
| ^~~~~~~~~~~
| cntnafardovom
