#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N = 1e5;
const int MAX_D = 1e5;
const int MOD = 1e9 + 7;
bool canWin[MAX_N + 1];
int countChildrenLosers[MAX_N + 1], add[MAX_N + 1], reach[MAX_N + 1], dp[MAX_D + 1][3];
vector<int> adj[MAX_N + 1];
void dfsGame( int u, int p ) {
canWin[u] = false;
countChildrenLosers[u] = 0;
for ( int v: adj[u] ) {
if ( v == p )
continue;
dfsGame( v, u );
canWin[u] |= (!canWin[v]);
countChildrenLosers[u] += (!canWin[v]);
}
}
void dfsCalcAdd( int u, int p ) {
if ( p == 0 ) {
add[u] = (canWin[u] ? -1 : 1);
reach[u] = u;
} else {
if ( canWin[u] ) {
if ( canWin[p] ) {
add[u] = -1;
reach[u] = u;
} else {
add[u] = add[p] - 1;
reach[u] = reach[p];
}
} else {
if ( countChildrenLosers[p] >= 2 ) {
add[u] = 1;
reach[u] = u;
} else {
add[u] = add[p] + 1;
reach[u] = reach[p];
}
}
}
for ( int v: adj[u] ) {
if ( v == p )
continue;
dfsCalcAdd( v, u );
}
}
int f[MAX_N + 1];
signed main() {
int n, d;
cin >> n >> d;
for ( int i = 0; i < n - 1; i++ ) {
int u, v;
cin >> u >> v;
adj[u].push_back( v );
adj[v].push_back( u );
/*adj[u + n].push_back( v + n );
adj[v + n].push_back( u + n );
adj[u + 2 * n].push_back( v + 2 * n );
adj[v + 2 * n].push_back( u + 2 * n );*/
}
/*int an = 0;
for ( int u = 1; u <= n; u++ ) {
for ( int v = n + 1; v <= 2 * n; v++ ) {
adj[u].push_back( v );
adj[v].push_back( u );
for ( int w = n + 1; w <= 2 * n; w++ ) {
for ( int t = 2 * n + 1; t <= 3 * n; t++ ) {
adj[w].push_back( t );
adj[t].push_back( w );
dfsGame( 1, 0 );
if ( canWin[1] ) {
an++;
printf( "W %d-%d %d-%d\n", u, v, w, t );
}
adj[w].pop_back();
adj[t].pop_back();
}
}
adj[u].pop_back();
adj[v].pop_back();
}
}
cout << an << "\n";*/
bool ok = true;
int winners[2] = { 0, 0 };
for ( int r = 1; r <= n; r++ ) {
dfsGame( r, 0 );
winners[0] += canWin[r];
if ( ok && !canWin[r] ) {
adj[r].push_back( n + 1 );
ok = false;
for ( int v = 1; v <= n; v++ ) {
dfsGame( v, 0 );
winners[1] += canWin[v];
}
adj[r].pop_back();
}
}
int dif = 0;
for ( int v = 1; v <= n; v++ ) {
adj[v].push_back( n + 1 );
int winners = 0;
for ( int r = 1; r <= n; r++ ) {
dfsGame( r, 0 );
//for ( int x = 1; x <= n; x++ )
// cout << canWin[x];
//cout << canWin[r] << "\n";
winners += canWin[r];
}
dif += (f[winners] == 0);
f[winners]++;
//cout << v << " " << winners;
// cout << "\n";
adj[v].pop_back();
}
if ( dif > 100 )
return 1;
dp[1][0] = 1;
//printf( "%d %d\n", winners[0], winners[1] );
for ( int i = 2; i <= d; i++ ) {
for ( int a = 0; a < 2; a++ ) {
int p1 = (n - winners[0]) * (n - winners[1]) % MOD;
int p0 = (n * n % MOD - p1 + MOD) % MOD;
dp[i][0] = (dp[i][0] + dp[i - 1][a] * p0) % MOD;
dp[i][1] = (dp[i][1] + dp[i - 1][a] * p1) % MOD;
}
//printf( "%d %d\n", dp[i][0], dp[i][1] );
}
dfsGame( 1, 0 );
dfsCalcAdd( 1, 0 );
int ans = 0;
for ( int a = 0; a < 2; a++ ) {
for ( int v = 1; v <= n; v++ ) {
if ( canWin[1] ) {
if ( canWin[v] )
ans = (ans + n * dp[d][a]) % MOD;
else {
ans = (ans + winners[a] * dp[d][a]) % MOD;
if ( reach[v] != 1 )
ans = (ans + (n - winners[a]) * dp[d][a]) % MOD;
}
} else {
if ( !canWin[v] ) {
if ( reach[v] == 1 )
ans = (ans + (n - winners[a]) * dp[d][a]) % MOD;
}
}
}
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Execution timed out |
1067 ms |
4444 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6608 KB |
Output is correct |
| 3 |
Runtime error |
11 ms |
16220 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
9 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
7 ms |
6608 KB |
Output is correct |
| 5 |
Correct |
7 ms |
6488 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
9 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
7 ms |
6608 KB |
Output is correct |
| 5 |
Correct |
7 ms |
6488 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6604 KB |
Output is correct |
| 7 |
Execution timed out |
1070 ms |
4620 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
9 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
7 ms |
6608 KB |
Output is correct |
| 5 |
Correct |
7 ms |
6488 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6604 KB |
Output is correct |
| 7 |
Execution timed out |
1070 ms |
4620 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
9 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
7 ms |
6608 KB |
Output is correct |
| 5 |
Correct |
7 ms |
6488 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6604 KB |
Output is correct |
| 7 |
Execution timed out |
1070 ms |
4620 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
7 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
9 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
7 ms |
6608 KB |
Output is correct |
| 5 |
Correct |
7 ms |
6488 KB |
Output is correct |
| 6 |
Correct |
8 ms |
6604 KB |
Output is correct |
| 7 |
Execution timed out |
1070 ms |
4620 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6488 KB |
Output is correct |
| 2 |
Execution timed out |
1067 ms |
4444 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
