#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;
}
Compilation message
startrek.cpp:246:1: error: extended character is not valid in an identifier
246 |
| ^
startrek.cpp:246:1: error: '\U000000a0' does not name a type
246 |
| ^
