Submission #865071

#TimeUsernameProblemLanguageResultExecution timeMemory
865071maks007Cat in a tree (BOI17_catinatree)C++14
0 / 100
0 ms348 KiB
// Bismi ALlah #include "bits/stdc++.h" using namespace std; #define int long long int dp[1501][1501]; signed main () { int n, d; cin >> n >> d; vector <int> g[n]; for(int i= 0; i < n; i ++) { for(int j = 0; j< d; j ++) dp[i][j] = -1e9; } function <void(int,int)> dfs=[&](int v, int p) { vector <int> child; for(auto u : g[v]) { if(u == p) continue; dfs(u, v); child.push_back(u); } if(child.size() == 0) { dp[v][0] = 1; return; } dp[v][0] = 1; for(auto i : child) { dp[v][0] += max(0LL, dp[i][d-1]); } for(int whichDist = 1; whichDist < d; whichDist ++) { for(auto which : child) { int sum = dp[which][whichDist-1]; for(auto other : child) { if(other == which) continue; sum += dp[other][d-2]; } dp[v][whichDist] = max(dp[v][whichDist], sum); } } }; for(int i = 1; i < n; i ++) { int p; cin >> p; g[i].push_back(p); g[p].push_back(i); } dfs(0, -1); int ans = -1e9; for(int i = 0; i < d; i ++) ans = max(ans, dp[0][i]); /* for(int i = 0; i < n; i ++) { for(int j = 0; j < d; j ++) { cout << i << " " << j << " " << dp[i][j] << "\n"; } }*/ cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...