#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mx = 1e5 + 5;
int sz[mx]{};
int cnt2[mx]{};
int win2[mx]{};
int cnt[mx]{};
int win[mx]{};
bool vis[mx]{};
vector<int> adj[mx]{};
int dfs(int v, int p) {
if (vis[v]) return 0;
sz[v] = 1;
for (auto& x : adj[v])
if (x != p)
sz[v] += dfs(x, v);
return sz[v];
}
void dfs2(int v, int p) {
//if all lead to win, it loses
if (vis[v]) return;
int cntlose = 0;
int a = 0, b = 0;
for (auto& x : adj[v]) {
if (x == p) continue;
dfs2(x, v);
if (win2[x]) a += cnt2[x];
else b += cnt2[x];
cntlose += !win2[x];
}
// cout << "a" << cntlose << "," << v << "," << a << "," << b << endl;
if (cntlose == 1) {
cnt2[v] = b;
}
if (cntlose == 0) {
cnt2[v] = a + 1;
}
win2[v] = cntlose ? 1 : 0;
}
void cd(int v) {
dfs(v, -1);
int N = sz[v];
int p = v;
bool cont = 1;
while (cont) {
cont = 0;
for (auto& x : adj[v]) {
if (sz[x] >= N / 2 && !vis[x] && x != p) {
p = v; v = x;
cont = 1;
break;
}
}
}
cnt2[v] = 0, win2[v] = 0;
vis[v] = 1;
int cntlose = 0, a = 0, b = 0;
for (auto& x : adj[v]) {
dfs2(x, v);
if (win2[x]) a += cnt2[x];
else b += cnt2[x];
cntlose += !win2[x];
}
for (auto& x : adj[v]) {
if (vis[x]) continue;
dfs2(x, v);
if (win2[x]) a -= cnt2[x];
else b -= cnt2[x];
cntlose -= !win2[x];
// cout << v << "," << cntlose << "," << a << "," << b << endl;
cnt2[v] = 0;
if (cntlose == 1) {
cnt2[v] = b;
}
if (cntlose == 0) {
cnt2[v] = a + 1;
}
win2[v] = cntlose ? 1 : 0;
cd(x);
dfs2(x, v);
if (win2[x]) a += cnt2[x];
else b += cnt2[x];
cntlose += !win2[x];
}
// cout << "fin: " << v << "," << cntlose << "," << a << "," << b << endl;
cnt[v] = 0;
if (cntlose == 1) {
cnt[v] = b;
}
if (cntlose == 0) {
cnt[v] = a + 1;
}
win[v] = cntlose ? 1 : 0;
vis[v] = 0;
}
const int mod = 1e9 + 7;
struct uwu {
int a = 0, b = 0, c = 0, d = 0;
};
uwu combine(uwu a, uwu b) {
uwu res;
res.a = a.a * b.a + a.c * b.c % mod;
res.b = a.a * b.b + a.c * b.d + a.b * (b.a + b.b + b.c + b.d) % mod;
res.c = a.c * b.a + a.a * b.c % mod;
res.d = a.c * b.b + a.a * b.d + a.d * (b.a + b.b + b.c + b.d) % mod;
return res;
}
uwu binpow(uwu a, int b) {
if (b == 1) return a;
uwu c = binpow(combine(a, a), b / 2);
if (b & 1) c = combine(c, a);
return c;
}
void solve() {
int N, D; cin >> N >> D;
for (int i = 0; i < N - 1; i++) {
int a, b; cin >> a >> b; a--;b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
cd(0);
int cntw = 0, cntl = 0;
uwu x;
for (int i = 0; i < N; i++) {
if (win[i]) {
cntw++;
x.a += cnt[i];
x.b += N - cnt[i];
} else {
cntl++;
x.c += cnt[i];
x.d += N - cnt[i];
}
}
x = binpow(x, D);
if (D == 0) {
cout << win[0] << endl;
} else if (D == 1) {
uwu v;
if (win[0]) {
v.a += cnt[0];
v.b += N - cnt[0];
} else {
v.c += cnt[0];
v.d += N - cnt[0];
}
// cout << v.c << "," << cntl << endl;
cout << (v.a * cntw + v.b * N + v.c * cntl) % mod << endl;
} else {
uwu v;
if (win[0]) {
v.a += cnt[0];
v.b += N - cnt[0];
} else {
v.c += cnt[0];
v.d += N - cnt[0];
}
v = combine(v, binpow(x, D - 1));
cout << (v.a * cntw + v.b * N + v.c * cntl) % mod << endl;
}
}
int32_t main() {
int t = 1;
//cin >> t;
while (t--)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 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 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Incorrect |
3 ms |
2644 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Incorrect |
3 ms |
2644 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Incorrect |
3 ms |
2644 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Incorrect |
3 ms |
2644 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
