Advertisement
libobil

Untitled

Dec 21st, 2022
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.17 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cassert>
  4. #include <numeric>
  5. #include <vector>
  6.  
  7. typedef long long llong;
  8. const int MAXN = 2000 + 10;
  9. const llong INF = 2e9 + 10;
  10.  
  11. int l[MAXN], n;
  12. int inputC[MAXN];
  13. int c[MAXN][MAXN];
  14. llong dpPlus[MAXN][MAXN];
  15. llong dpMinus[MAXN][MAXN];
  16. bool blPlus[MAXN][MAXN];
  17. bool blMinus[MAXN][MAXN];
  18. std::vector <int> g[MAXN];
  19.  
  20. llong plus(int node, int incoming);
  21. llong minus(int node, int wanted);
  22.  
  23. void dfs(int node, int p)
  24. {
  25. for (int &i : g[node])
  26. {
  27. if (i == p)
  28. {
  29. std::swap(i, g[node].back());
  30. g[node].pop_back();
  31. break;
  32. }
  33. }
  34.  
  35. for (const int &i : g[node])
  36. {
  37. dfs(i, node);
  38. }
  39. }
  40.  
  41. llong plus(int node, int incoming)
  42. {
  43. if (incoming >= n+1) return 0;
  44. if (g[node].empty())
  45. {
  46. assert(incoming >= 1);
  47. return 0;
  48. }
  49.  
  50. if (blPlus[node][incoming]) return dpPlus[node][incoming];
  51. blPlus[node][incoming] = true;
  52. dpPlus[node][incoming] = minus(node, 0);
  53.  
  54. llong lsum = 0;
  55. for (const int &i : g[node])
  56. {
  57. if (incoming == 1) lsum += minus(i, 0);
  58. else lsum += plus(i, incoming - 1);
  59. }
  60.  
  61. dpPlus[node][incoming] = std::min(dpPlus[node][incoming], std::min(lsum, INF));
  62. return dpPlus[node][incoming];
  63. }
  64.  
  65. llong minus(int node, int wanted)
  66. {
  67. if (wanted >= n+1) return INF;
  68. if (g[node].empty())
  69. {
  70. if (l[node] >= wanted + 1) return c[node][wanted + 1];
  71. return INF;
  72. }
  73.  
  74. if (blMinus[node][wanted]) return dpMinus[node][wanted];
  75. blMinus[node][wanted] = true;
  76. dpMinus[node][wanted] = minus(node, wanted + 1);
  77.  
  78. llong sum = 0;
  79. for (const int &i : g[node])
  80. {
  81. if (wanted >= 1) sum += plus(i, wanted);
  82. else sum += minus(i, 0);
  83. }
  84.  
  85. if (wanted + 1 <= l[node])
  86. {
  87. dpMinus[node][wanted] = std::min(dpMinus[node][wanted], sum + c[node][wanted + 1]);
  88. }
  89.  
  90. for (const int &i : g[node])
  91. {
  92. llong curr = sum + minus(i, wanted + 1);
  93. if (wanted == 0) curr -= minus(i, 0);
  94. else curr -= plus(i, wanted);
  95.  
  96. if (curr < dpMinus[node][wanted])
  97. {
  98. dpMinus[node][wanted] = curr;
  99. }
  100. }
  101.  
  102. return dpMinus[node][wanted];
  103. }
  104.  
  105. void solve()
  106. {
  107. for (int i = 1 ; i <= n ; ++i)
  108. {
  109. for (int j = n + 1 ; j >= l[i] + 1 ; --j) c[i][j] = INF;
  110. for (int j = l[i] ; j >= 1 ; --j)
  111. {
  112. c[i][j] = std::min(c[i][j + 1], inputC[j]);
  113. }
  114. }
  115.  
  116. dfs(1, 0);
  117. llong res = minus(1, 0);
  118. if (res >= INF) std::cout << -1 << '\n';
  119. else std::cout << res << '\n';
  120. }
  121.  
  122. void read()
  123. {
  124. std::cin >> n;
  125. for (int i = 1 ; i <= n ; ++i) std::cin >> inputC[i];
  126. for (int i = 1 ; i <= n ; ++i) std::cin >> l[i];
  127. for (int i = 2 ; i <= n ; ++i)
  128. {
  129. int x, y;
  130. std::cin >> x >> y;
  131. g[x].push_back(y);
  132. g[y].push_back(x);
  133. }
  134.  
  135. }
  136.  
  137. void fastIO()
  138. {
  139. std::ios_base :: sync_with_stdio(0);
  140. std::cout.tie(nullptr);
  141. std::cin.tie(nullptr);
  142. }
  143.  
  144. int main()
  145. {
  146. fastIO();
  147. read();
  148. solve();
  149.  
  150. return 0;
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement