Advertisement
Guest User

Untitled

a guest
Jan 16th, 2019
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.69 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int N = 2e5 + 7;
  5. int n, d;
  6. vector <int> g[N];
  7. vector <int> dp[N];
  8. void dfs(int u, int p) {
  9. int mx = -1;
  10. for (int v : g[u]) {
  11. if (v != p) {
  12. dfs(v, u);
  13. if (mx == -1 || dp[mx].size() < dp[v].size()) {
  14. mx = v;
  15. }
  16. }
  17. }
  18. if (mx == -1) {
  19. dp[u] = {1};
  20. }
  21. else {
  22. swap(dp[u], dp[mx]);
  23. int uh = dp[u].size();
  24. int t;
  25. if (uh < d) t = 1;
  26. else t = dp[u][uh - d] + 1;
  27. for (int v : g[u]) {
  28. if (v != p && v != mx) {
  29. int vh = dp[v].size();
  30. for (int i = 0; i + 1 < vh; ++i) {
  31. dp[v][i + 1] = max(dp[v][i + 1], dp[v][i]);
  32. }
  33. vector <int> tmp(vh);
  34. for (int h = 1; h <= (int)dp[v].size(); ++h) {
  35. //h <= nh
  36. int nh = max(h, d - h);
  37. if (nh <= vh) {
  38. tmp[vh - h] = max(tmp[vh - h], dp[u][uh - h] + dp[v][vh - nh]);
  39. }
  40. }
  41. for (int nh = 1; nh <= (int)dp[v].size(); ++nh) {
  42. //h >= nh
  43. int h = max(nh, d - nh);
  44. if (h <= uh) {
  45. tmp[vh - nh] = max(tmp[vh - nh], dp[u][uh - h] + dp[v][vh - nh]);
  46. }
  47. }
  48. for (int h = 1; h <= vh; ++h) {
  49. dp[u][uh - h] = max(dp[u][uh - h], tmp[vh - h]);
  50. }
  51. for (int i = uh - vh; i + 1 < uh; ++i) {
  52. dp[u][i + 1] = max(dp[u][i + 1], dp[u][i]);
  53. }
  54. }
  55. }
  56. dp[u].push_back(t);
  57. for (int v : g[u]) {
  58. if (v != p && v != mx) {
  59. int vh = dp[v].size();
  60. if (vh >= d) {
  61. dp[u].back() += dp[v][vh - d];
  62. }
  63. }
  64. }
  65. dp[u][uh] = max(dp[u][uh], dp[u][uh - 1]);
  66. }
  67. #ifdef HOME
  68. cout << u << " : ";
  69. for (int i = (int)dp[u].size() - 1; i >= 0; --i) cout << dp[u][i] << ' ';
  70. cout << '\n';
  71. #endif
  72. }
  73. signed main() {
  74. #ifdef HOME
  75. freopen("input.txt", "r", stdin);
  76. #else
  77. ios_base::sync_with_stdio(0); cin.tie(0); cout.precision(20);
  78. #endif
  79. cin >> n >> d;
  80. for (int i = 1; i < n; ++i) {
  81. int v;
  82. cin >> v;
  83. g[v].push_back(i);
  84. g[i].push_back(v);
  85. }
  86. dfs(0, 0);
  87. int ans = -1;
  88. for (int e : dp[0]) ans = max(ans, e);
  89. cout << ans << '\n';
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement