제출 #1295898

#제출 시각아이디문제언어결과실행 시간메모리
1295898avighnaCat in a tree (BOI17_catinatree)C++20
0 / 100
2 ms568 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, d; cin >> n >> d; vector<vector<int>> adj(n); for (int i = 1, p; i < n; ++i) { cin >> p; adj[p].push_back(i); } if (d >= n) { cout << "1\n"; return 0; } // dp[u][d] = in the subtree of u, nodes are at least d away from the root auto dfs = [&](auto &&self, int u) -> vector<int> { vector<int> ch_dp(n), dp(n); int sum = 0; for (int &i : adj[u]) { vector<int> res = self(self, i); sum += res[d - 1]; for (int d = 0; d < n; ++d) { for (int l = 0; 2 * l <= d; ++l) { dp[d] = max(dp[d], res[l] + ch_dp[d - l]); } } for (int i = 0; i < n; ++i) { ch_dp[i] += res[i]; } } dp[0] = max(dp[0], sum + 1); return dp; }; auto dp = dfs(dfs, 0); cout << dp[0] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...