#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];
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 lgPut( int x, int n ) {
if ( n == 0 )
return 1;
int p = lgPut( x, n / 2 );
p = (long long)p * p % MOD;
if ( n % 2 == 1 )
p = (long long)p * x % MOD;
return p;
}
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";*/
int losers = 0, winners = 0, reach1Losers = 0, reach1Winners = 0;
for ( int r = 1; r <= n; r++ ) {
dfsGame( r, 0 );
dfsCalcAdd( r, 0 );
losers += !canWin[r];
winners += canWin[r];
for ( int v = 1; v <= n; v++ ) {
reach1Losers += (!canWin[r] && !canWin[v] && reach[v] == 1);
reach1Winners += (canWin[r] && !canWin[v] && reach[v] == 1);
}
}
/*dp[0] = losers;
for ( int i = 1; i < d; i++ )
dp[i] = (losers * lgPut( n, 2 * d ) + (reach1Winners - reach1Losers + MOD) * dp[i - 1]) % MOD;
dfsGame( 1, 0 );
dfsCalcAdd( 1, 0 );
int ans = (canWin[1] ? 0 : lgPut( n, 2 * d ) );
for ( int v = 1; v <= n; v++ ) {
if ( canWin[1] ) {
if ( !canWin[v] && reach[v] == 1 )
ans = (ans + dp[d - 1]) % MOD;
} else {
if ( !canWin[v] && reach[v] == 1 )
ans = (ans - dp[d - 1]) % MOD;
}
}*/
int ans = 0;
cout << (lgPut( n, 2 * d ) - ans + MOD) % MOD << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
