#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ld long double
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]= {0, 1, 0, -1}, dy[4]= {1, 0, -1, 0};
int ddx[8]={1, 1, 0, -1, -1, -1, 0, 1}, ddy[8]={0, 1, 1, 1, 0, -1, -1, -1};
const int mxN=100025;
const int mxM=300005;
const int mxK=1000000000;
const ll MOD=1000'000'007;
const ll INF=1000000000000000005;
ll N, D;
vector <int> v[mxN];
int outw[mxN];
int downw[mxN], upw[mxN];
bool W[mxN];
ll degL[mxN];
ll leafw2[mxN], sizl2[mxN], par2[mxN];
ll numw;
int match[mxN];
ll swapL1[mxN];
void dfs_downw(int now, int pre)
{
for(int nxt : v[now]) if(nxt!=pre)
{
dfs_downw(nxt, now);
}
downw[now]=(outw[now]==0 ? 1 : 0);
if(now!=1) outw[pre]+=downw[now];
}
void dfs_upw(int now, int pre)
{
if(now!=1)
{
upw[now]=(outw[pre]-downw[now]==0 ? 1 : 0);
outw[now]+=upw[now];
}
for(int nxt : v[now]) if(nxt!=pre)
{
dfs_upw(nxt, now);
}
}
int findpar(int a)
{
return (par2[a]==a ? a : par2[a]=findpar(par2[a]));
}
void onion(int a, int b)
{
int p=findpar(a), q=findpar(b);
par2[p]=q; sizl2[q]+=sizl2[p]; leafw2[q]+=leafw2[p];
}
int dfs_match(int now, int pre)
{
for(int nxt : v[now]) if(nxt!=pre && W[nxt] && degL[nxt]==0)
{
int tmp=dfs_match(nxt, now);
if(tmp!=0) match[now]=tmp, match[tmp]=now;
}
if(match[now]) return 0;
else return now;
}
int dfs_swap(int now)
{
if(swapL1[now]!=0) return swapL1[now];
ll sum=1;
for(int nxt : v[match[now]]) if(nxt!=now && W[nxt] && degL[nxt]==0)
{
sum+=dfs_swap(nxt);
}
return swapL1[now]=sum;
}
ll f(ll a)
{
return (a%MOD+MOD)%MOD;
}
ll mypow(ll a, ll b)
{
if(b==0) return 1;
if(b==1) return f(a);
ll tmp=mypow(a, b/2);
tmp*=tmp; tmp%=MOD;
if(b%2) tmp*=a; tmp%=MOD;
return tmp;
}
int main()
{
gibon
cin >> N >> D;
for(int i=1;i<N;i++)
{
int a, b; cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs_downw(1, -1);
dfs_upw(1, -1);
for(int i=1;i<=N;i++)
{
W[i]=(outw[i]>=1);
numw+=W[i];
}
for(int i=1;i<=N;i++) for(int ele : v[i]) if(!W[ele]) degL[i]++;
for(int i=1;i<=N;i++)
{
par2[i]=i;
if(degL[i]==1) leafw2[i]=1;
if(!W[i]) sizl2[i]=1;
}
for(int i=1;i<=N;i++) for(int ele : v[i]) if(degL[ele]<3 && !W[i]) onion(i, ele);
for(int i=1;i<=N;i++) if(W[i] && degL[i]==0 && match[i]==0) dfs_match(i, -1);
for(int i=1;i<=N;i++) if(W[i] && degL[i]==0) dfs_swap(i);
ll k1=numw, k2=0;
for(int i=1;i<=N;i++) k2-=swapL1[i]; k2=f(k2);
for(int i=1;i<=N;i++) if(findpar(i)==i) k2+=sizl2[i]*(sizl2[i]-leafw2[i]), k2=f(k2);
ll recur;
if(D==0) recur=numw;
else recur=(N*N%MOD*k1%MOD+N*k2%MOD)%MOD*(mypow(N, 2*(D-1))+mypow(f(k2), D-1))%MOD*mypow(f(N*N+k2), MOD-2)%MOD+mypow(MOD-1, D-1)*numw%MOD*mypow(k2, D-1)%MOD;
recur=f(recur);
ll powN=mypow(N, 2*D-1);
if(W[1])
{
ll ans=powN*N%MOD;
if(degL[1]==0) ans-=(powN-recur)*swapL1[1]; ans=f(ans);
if(degL[1]==1) ans-=(powN-recur)*sizl2[findpar(1)]; ans=f(ans);
cout << ans;
}
else
{
ll ans=0;
ans+=(powN-recur)*sizl2[findpar(1)];
cout << f(ans);
}
}
Compilation message
startrek.cpp: In function 'll mypow(ll, ll)':
startrek.cpp:92:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
92 | if(b%2) tmp*=a; tmp%=MOD;
| ^~
startrek.cpp:92:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
92 | if(b%2) tmp*=a; tmp%=MOD;
| ^~~
startrek.cpp: In function 'int main()':
startrek.cpp:123:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
123 | for(int i=1;i<=N;i++) k2-=swapL1[i]; k2=f(k2);
| ^~~
startrek.cpp:123:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
123 | for(int i=1;i<=N;i++) k2-=swapL1[i]; k2=f(k2);
| ^~
startrek.cpp:133:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
133 | if(degL[1]==0) ans-=(powN-recur)*swapL1[1]; ans=f(ans);
| ^~
startrek.cpp:133:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
133 | if(degL[1]==0) ans-=(powN-recur)*swapL1[1]; ans=f(ans);
| ^~~
startrek.cpp:134:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
134 | if(degL[1]==1) ans-=(powN-recur)*sizl2[findpar(1)]; ans=f(ans);
| ^~
startrek.cpp:134:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
134 | if(degL[1]==1) ans-=(powN-recur)*sizl2[findpar(1)]; ans=f(ans);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
