#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
int tp[N], tpr[N];
int crit[N], critr[N];
vector<int> gr[N];
void add(long long &x, long long y){
y%=MOD;
x+=y;
if(x>=MOD)
x-=MOD;
if(x<0)
x+=MOD;
}
void add(int &x, long long y){
y%=MOD;
x+=y;
if(x>=MOD)
x-=MOD;
if(x<0)
x+=MOD;
}
void dfs(int nod, int dad){
tp[nod] = 0;
int nr0 = 0, sum = 0, unq = 0;
for(auto x:gr[nod]){
if(x != dad){
dfs(x, nod);
if(tp[x] == 0)
nr0++, unq = crit[x];
sum += crit[x];
}
}
if(nr0 == 0){
tp[nod] = 0;
crit[nod] = sum + 1;
}
else if(nr0 == 1){
tp[nod] = 1;
crit[nod] = unq;
}
else{
tp[nod] = 1;
crit[nod] = 0;
}
}
void changeroot(int nod, int dad){
int OLDTP = tp[nod], OLDCRIT = crit[nod];
int nr0 = 0, sum = 0, unq = 0;
for(auto x:gr[nod]){
if(tp[x] == 0 )
nr0++, unq = crit[x];
sum += crit[x];
}
if(nr0 == 0)
tp[nod] = 0;
else
tp[nod] = 1;
if(tp[nod] == 0){
crit[nod] = sum + 1;
}
else if(tp[nod] == 1){
crit[nod] = 0;
if(nr0 == 1)
crit[nod] = unq;
}
critr[nod] = crit[nod];
tpr[nod] = tp[nod];
for(auto x:gr[nod]){
if(x == dad)
continue;
int oldtp = tp[nod], oldcrit = crit[nod];
if(tp[nod] == 0){
tp[nod] = 0;
crit[nod] = sum + 1 - crit[x];
}
else{
if(tp[x] == 1){
tp[nod] = 1;
crit[nod] = oldcrit;
}
else{
if(nr0 == 1){
tp[nod] = 0;
crit[nod] = sum + 1 - crit[x];
}
else if(nr0 == 2){
tp[nod] = 1;
int othunq = 0;
for(auto vc:gr[nod]){
if(vc == x)
continue;
if(tp[vc] == 0)
othunq = crit[vc];
}
crit[nod] = othunq;
}
else if(nr0 >= 3){
tp[nod] = 1;
crit[nod] = 0;
}
}
}
changeroot(x, nod);
tp[nod] = oldtp;
crit[nod] = oldcrit;
}
tp[nod] = OLDTP;
crit[nod] = OLDCRIT;
}
long long dp[N][2];
int main()
{
freopen(".in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n, d;
cin>>n>>d;
for(int i = 1; i < n; i++){
int u, v;
cin>>u>>v;
gr[u].push_back(v);
gr[v].push_back(u);
}
dfs(1, 0);
changeroot(1, 0);
long long nr0 = 0, sumc0= 0, nr1 = 0, sumc1= 0;
for(int i = 1; i<=n; i++){
if(tpr[i] == 0){
nr0++;
add(sumc0, critr[i]);
}
else{
nr1++;
add(sumc1, critr[i]);
}
cerr<<tpr[i]<<" "<<critr[i]<<"\n";
}
dp[0][0] = nr0;
dp[0][1] = nr1;
for(int i = 1; i <d; i++){
dp[i][0] = 0;
//vine din 0
add(dp[i][0], 1LL * sumc0 * dp[i-1][1]);
add(dp[i][0], 1LL * (1LL*n*n%MOD - sumc0 + MOD)%MOD * ((dp[i-1][0] + dp[i-1][1])%MOD));
//vine din 1
add(dp[i][0], 1LL * sumc1 * dp[i-1][0]);
dp[i][1] = 0;
//vine din 0
add(dp[i][1], 1LL * sumc0 * dp[i-1][0]);
//vine din 1
add(dp[i][1], 1LL * sumc1 * dp[i - 1][1]);
add(dp[i][1], 1LL * (1LL*n*n%MOD - sumc1 + MOD)%MOD * ((dp[i-1][0] + dp[i-1][1])%MOD));
}
long long ans = 0;
if(tpr[1] == 0){
ans = 1LL * critr[1] * dp[d-1][0] % MOD;
}
else{
ans = 1LL * critr[1] * dp[d - 1][1] % MOD;
add(ans, 1LL * (n - critr[1] + MOD)%MOD * ((dp[d-1][0] + dp[d-1][1])%MOD));
}
cout<<ans;
return 0;
}
Compilation message
startrek.cpp: In function 'int main()':
startrek.cpp:120:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | freopen(".in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5324 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
5304 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5324 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
