#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 = 1001, 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];
bool dp[N], dp2[N];
int chosen = -1;
void dfs(int v, int p) {
dp[v] = false;
for (int to : g[v]) {
if (to != p) {
dfs(to, v);
if (!dp[to]) {
++cntLoosing[v];
dp[v] = true;
}
}
}
}
void gfs(int v, int p) {
if (!dp[v] && p != -1 && cntLoosing[p] == 1) {
dp[v] = true;
}
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;
}
}
}
if (v == chosen) {
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);
gfs(0, -1);
cntWin = count(dp, dp + n, true);
int ans = (dp[0] * cntWin * n);
for (chosen = 0; chosen < n; ++chosen) {
dfs2(0, -1);
if (dp2[0]) {
ans += (n - cntWin);
}
}
cout << ans;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |