/*
Author: AquaBlaze
Time: 2021-01-03 18:10:22
Generated by powerful Codeforces Tool :^)
You can download the binary file in here https://github.com/xalanq/cf-tool (Windows, macOS, Linux)
Keqing best girl :)
Nephren will always be in my heart
*/
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())
#define pc(x) putchar(x)
#define MP make_pair
#define MT make_tuple
using namespace std;
typedef long long i64;
typedef tuple<int,int,int> iii;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int N = 100005;
const int mod = 1000000007;
int add(int a, int b){ return ((a+=b)>=mod)?a-mod:a; }
void adding(int &a, int b){ a = add(a, b); }
int mul(int a, int b){ return a*1ll*b%mod; }
pii operator + (const pii& A, const pii& B){
return pii(add(A.x,B.x), add(A.y,B.y));
}
pii operator - (const pii& A, const pii& B){
return pii(add(A.x,mod-B.x), add(A.y,mod-B.y));
}
inline pii& operator += (pii& A, const pii& B){
A = A+B;
return A;
}
inline pii& operator -= (pii& A, const pii& B){
A = A-B;
return A;
}
vi g[N];
pii dp[N][2], final_dp[N][2], sum[N][2], lose[N][2];
int result[N], final_res[N];
void adjust(int u){
if(result[u]) dp[u][1]+=pii(1,1);
else{
dp[u][1]+=pii(0,1);
dp[u][0]+=pii(1,0);
}
}
void dejust(int u){
if(result[u]) dp[u][1]-=pii(1,1);
else{
dp[u][1]-=pii(0,1);
dp[u][0]-=pii(1,0);
}
}
void add_node(int u, int v){
dejust(u);
if(result[u]==0){
if(!result[v]){
dp[u][1] = sum[u][0]+sum[u][1]+dp[v][0];
dp[u][0] = dp[v][1];
}else{
dp[u][1] += dp[v][0];
dp[u][0] += dp[v][1];
}
}else if(result[u]==1){
if(!result[v]){
dp[u][0] -= lose[u][1];
dp[u][1] += lose[u][1]+dp[v][0]+dp[v][1];
}else{
dp[u][1] += dp[v][0]+dp[v][1];
}
}else{
dp[u][1] += dp[v][0]+dp[v][1];
}
if(!result[v]){
FOR(i,0,1) lose[u][i]+=dp[v][i];
}
result[u] += !result[v];
adjust(u);
FOR(i,0,1) sum[u][i]+=dp[v][i];
}
void sub_node(int u, int v){
dejust(u);
if(result[u]==0){
if(!result[v]){
assert(0);
}else{
dp[u][1] -= dp[v][0];
dp[u][0] -= dp[v][1];
}
}else if(result[u]==1){
if(!result[v]){
dp[u][0] = sum[u][1]-dp[v][1];
dp[u][1] = sum[u][0]-dp[v][0];
}else{
dp[u][1] -= dp[v][0]+dp[v][1];
}
}else if(result[u]==2){
if(!result[v]){
dp[u][1] -= lose[u][0]+lose[u][1];
dp[u][1] += lose[u][0]-dp[v][0];
dp[u][0] += lose[u][1]-dp[v][1];
}else{
dp[u][1] -= dp[v][0]+dp[v][1];
}
}else{
dp[u][1] -= dp[v][0]+dp[v][1];
}
if(!result[v]){
FOR(i,0,1) lose[u][i]-=dp[v][i];
}
result[u] -= !result[v];
adjust(u);
FOR(i,0,1) sum[u][i]-=dp[v][i];
}
void dfs(int u, int p){
for(int &e : g[u]){
if(e == p){
swap(e, g[u].back());
g[u].pop_back();
break;
}
}
for(const int &e : g[u]){
dfs(e, u);
}
adjust(u);
for(const int &e : g[u]){
add_node(u, e);
}
}
void tour(int u){
final_res[u] = result[u];
FOR(i, 0, 1) final_dp[u][i]=dp[u][i];
for(const int &e : g[u]){
sub_node(u, e);
add_node(e, u);
tour(e);
sub_node(e, u);
add_node(u, e);
}
}
void solve(){
int n;
i64 d;
cin >> n >> d;
FOR(i, 2, n){
int a, b;
cin >> a >> b;
g[a].eb(b);
g[b].eb(a);
}
dfs(1, -1);
tour(1);
assert(dp[1][0]==final_dp[1][0]);
assert(dp[1][1]==final_dp[1][1]);
vvi m(2, vi(2,0));
vi res(2, 0);
ROF(i, n, 1){
int r = final_res[i];
res[1-r]++;
FOR(j, 0, 1){
adding(m[j^1][0], final_dp[i][j].x);
adding(m[j^1][1], final_dp[i][j].y);
}
}
FOR(t, 2, d){
vi tmp(2, 0);
FOR(i, 0, 1){
FOR(j, 0, 1){
adding(tmp[i], mul(res[j], m[i][j]));
}
}
res = tmp;
}
int ans = 0;
adding(ans, mul(final_dp[1][1].x, res[0]));
adding(ans, mul(final_dp[1][1].y, res[1]));
printf("%d",ans);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
/*
*
*
*
*
*
*
*
*
*
*
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5356 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2668 KB |
Output is correct |
| 3 |
Execution timed out |
1091 ms |
2668 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5356 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5356 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5356 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5356 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5356 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
5356 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
