#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template <typename T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
bool ckmx(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<typename T>
bool ckmn(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;
#define mp(x, y) make_pair(x, y)
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
const int N = 100001, mod = 1e9 + 7;
int mul(int a, int b) {
return a * (ll)b % mod;
}
int add(int a, int b) {
return a + b >= mod ? a + b - mod : a + b;
}
int fastp(int a, ll p) {
int ans = 1;
for (; p > 0; a = mul(a, a), p >>= 1) {
if (p & 1) {
ans = mul(ans, a);
}
}
return ans;
}
int inv(int a) {
return fastp(a, mod - 2);
}
vector<int> g[N];
int cntLoosing[N], dpWin[N], dpLose[N], grandpa[N], depth[N];
bool dp[N], dp2[N];
int chosen = -1;
void dfs(int v, int p, int pp) {
dp[v] = false;
grandpa[v] = pp;
if (p != -1)
depth[v] = depth[p] + 1;
bool oh = false;
for (int to : g[v]) {
if (to != p) {
oh = true;
dfs(to, v, (pp == -1 ? to : pp));
if (!dp[to]) {
dpWin[v] = add(dpWin[v], dpLose[to]);
dp[v] = true;
} else {
dpLose[v] = add(dpLose[v], dpWin[to]);
}
}
}
if (!oh)
dpLose[v] = 1;
}
void gfs(int v, int p) {
for (int to : g[v]) {
if (to != p) {
cntLoosing[v] += !dp[to];
} else if (!dp[p] || cntLoosing[p] == 1 && !dp[v]){
cntLoosing[v] += 1;
}
}
dp[v] = cntLoosing[v];
for (int to : g[v]) {
if (to != p) {
gfs(to, v);
}
}
}
void dfs2(int v, int p) {
dp2[v] = false;
for (int to : g[v]) {
if (to != p) {
dfs2(to, v);
if (!dp2[to]) {
dp2[v] = true;
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll d;
cin >> n >> d;
if (n == 2) {
cout << fastp(4, d);
return 0;
}
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
--a, --b;
g[a].push_back(b);
g[b].push_back(a);
}
if (d == 1) {
int cntWin = 0;
dfs(0, -1, -1);
gfs(0, -1);
cntWin = count(dp, dp + n, true);
int ans = (dp[0] * mul(cntWin, n));
dfs2(0, -1);
for (int v = 0; v < n; ++v) {
if (dp2[v]) {
ans = add(ans, (n - cntWin) * dp2[0]);
} else {
if (dp2[0]) {
if (dpWin[0] != dpLose[v] || depth[v] % 2 == 0) {
ans = add(ans, n - cntWin);
}
} else {
if (v == 0) {
ans = add(ans, n - cntWin);
}
else if (grandpa[v] != v && dpWin[grandpa[v]] == dpLose[v]) {
ans = add(ans, n - cntWin);
}
}
}
}
cout << ans;
}
return 0;
}
Compilation message
startrek.cpp: In function 'void gfs(int, int)':
startrek.cpp:99:49: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
99 | } else if (!dp[p] || cntLoosing[p] == 1 && !dp[v]){
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~
| # |
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 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 6 |
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 |
- |
