Submission #577814

#TimeUsernameProblemLanguageResultExecution timeMemory
577814tengiz05Star Trek (CEOI20_startrek)C++17
45 / 100
102 ms20664 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; constexpr int P = 1E9 + 7; i64 power(i64 a, i64 b) { i64 res = 1; for (; b > 0; a = a * a % P, b /= 2) { if (b % 2) { res = res * a % P; } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; i64 D; cin >> n >> D; if (n == 2) { cout << power(4, D) << "\n"; return 0; } vector<vector<int>> e(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; e[u].push_back(v); e[v].push_back(u); } vector<bool> win(n); function<void(int, int)> dfs = [&](int u, int p) { win[u] = false; for (int v : e[u]) { if (v != p) { dfs(v, u); win[u] = win[u] | (!win[v]); } } }; dfs(0, -1); int c[2] {}; dfs = [&](int u, int p) { c[win[u]]++; int cnt = 0; for (int v : e[u]) { cnt += win[v] == 0; } for (int v : e[u]) { if (v != p) { bool wu = win[u]; bool wv = win[v]; cnt -= !wv; win[u] = !!cnt; win[v] = win[v] | (!win[u]); dfs(v, u); win[u] = wu; win[v] = wv; cnt += !wv; } } }; dfs(0, -1); vector dp(2, vector<i64>(n, 0)); dfs = [&](int u, int p) { dp[1][u] = (c[0] + win[u] * c[1]) % P; dp[0][u] = (!win[u]) * c[1] % P; int cnt = 0; for (int v : e[u]) { if (v != p) { cnt += !win[v]; } } for (int v : e[u]) { if (v != p) { dfs(v, u); cnt -= !win[v]; dp[1][u] = (dp[1][u] + dp[0][v] + (!!cnt) * dp[1][v]) % P; dp[0][u] = (dp[0][u] + (!cnt) * dp[1][v]) % P; cnt += !win[v]; } } }; dfs(0, -1); cout << dp[1][0] << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...