Advertisement
Guest User

Untitled

a guest
Jan 28th, 2020
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.26 KB | None | 0 0
  1. /*#pragma GCC optimize("Ofast,no-stack-protector")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  3. #pragma GCC optimize("unroll-loops")
  4. #pragma GCC optimize("fast-math")*/
  5. #include<bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using ld = long double;
  11. using ull = unsigned long long;
  12.  
  13.  
  14. #define int long long
  15. // #define double ld
  16. #define F first
  17. #define S second
  18. #define all(v) v.begin(), v.end()
  19. #define rall(v) v.rbegin(), v.rend()
  20.  
  21. void accell() {
  22. cin.tie(0);
  23. cout.tie(0);
  24. ios_base::sync_with_stdio(0);
  25. }
  26.  
  27. int n, m, k;
  28. const int N = 2e5;
  29.  
  30.  
  31. struct MM {
  32. int d = 0, w = 0;
  33. };
  34.  
  35.  
  36. struct item {
  37. item *l, *r;
  38. int cnt;
  39. int pr;
  40. int mx;
  41. int add;
  42. int val;
  43. int d;
  44. item (int key, int nk) {
  45. mx = key;
  46. d = nk;
  47. val = key;
  48. add = 0;
  49. pr = rand();
  50. cnt = 1;
  51. l = r = nullptr;
  52. }
  53. item () {
  54. l = r = nullptr;
  55. pr = rand();
  56. val = d = mx = cnt = add = 0;
  57. }
  58. };
  59.  
  60.  
  61. int _cnt(item *it) {
  62. return it ? it->cnt : 0;
  63. }
  64. int _mx(item *it) {
  65. return it ? it->mx : 0;
  66. }
  67. void upd_cnt(item *it) {
  68. if (it) {
  69. it->cnt = _cnt(it->l) + _cnt(it->r) + 1;
  70. it->mx = max(_mx(it->l), _mx(it->r));
  71. it->mx = max(it->val, it->mx);
  72. }
  73. }
  74.  
  75. void push(item *it) {
  76. if (!it) return;
  77. if (it->l) it->l->add += it->add, it->l->val += it->add, it->l->mx += it->add;
  78. if (it->r) it->r->add += it->add, it->r->val += it->add, it->r->mx += it->add;
  79. it->add = 0;
  80. }
  81.  
  82. void merge(item *&it, item *l, item *r) {
  83. push(l);
  84. push(r);
  85. if (!l || !r)
  86. it = l ? l : r;
  87. else if (l->pr > r->pr)
  88. merge(l->r, l->r, r), it = l;
  89. else
  90. merge(r->l, l, r->l), it = r;
  91. upd_cnt(it);
  92. }
  93. void split(item *it, item *&l, item *&r, int key, int add = 0) {
  94. if (!it) {
  95. l = r = nullptr;
  96. return;
  97. }
  98. push(it);
  99. int ck = _cnt(it->l) + add;
  100. if (key <= ck)
  101. split(it->l, l, it->l, key, add), r = it;
  102. else
  103. split(it->r, it->r, r, key, add + _cnt(it->l) + 1), l = it;
  104. upd_cnt(it);
  105. }
  106. void split1(item *it, item *&l, item *&r, int key) {
  107. if (!it) {
  108. l = r = nullptr;
  109. return;
  110. }
  111. push(it);
  112. int ck = it->d;
  113. if (key <= ck)
  114. split1(it->l, l, it->l, key), r = it;
  115. else
  116. split1(it->r, it->r, r, key), l = it;
  117. upd_cnt(it);
  118. }
  119.  
  120.  
  121. void out(item *it, vector<pair<int, int> >&x) {
  122. if (!it)
  123. return;
  124. push(it);
  125. out(it->l, x);
  126. x.push_back({it->d, it->val});
  127. out(it->r, x);
  128. }
  129.  
  130.  
  131. map<int, int>mp[N];
  132. item *dp[N];
  133. vector<int>g[N];
  134. MM a[N];
  135.  
  136. void insert(item *it, pair<int, int>x) {
  137. item *f1 = nullptr, *f2 = nullptr;
  138. split1(it, f1, f2, x.first);
  139. merge(it, f1, new item(x.second, x.first));
  140. merge(it, it, f2);
  141. }
  142.  
  143. void print(item *it) {
  144. if (!it)
  145. return;
  146. push(it);
  147. print(it->l);
  148. cout << it->d << ' ' << it->val << endl;
  149. print(it->r);
  150. }
  151.  
  152.  
  153. void dfs(int v, int p = -1) {
  154. dp[v] = new item(0, 0);
  155. int cur = v;
  156. for (int to : g[v]) {
  157. if (to != p) {
  158. dfs(to, v);
  159. if (_cnt(dp[to]) > _cnt(dp[cur])) {
  160. cur = to;
  161. }
  162. }
  163. }
  164. int nd = a[v].w;
  165. for (int to : g[v]) {
  166. if (to != p) {
  167. item *f1 = nullptr;
  168. item *f2 = nullptr;
  169. split(dp[to], f1, f2, a[v].d + 1);
  170. nd += _mx(f1);
  171. merge(dp[to], f1, f2);
  172. }
  173. }
  174. cout << endl;
  175. cout << a[v].d << ' ' << nd << ' ' << v << endl;
  176. swap(dp[v], dp[cur]);
  177. for (int to : g[v]) {
  178. if (to != p && to != cur) {
  179. vector<pair<int, int> > res;
  180. out(dp[to], res);
  181. vector<int>care((int)res.size());
  182. for (int i = 0; i < res.size(); ++i) {
  183. item *f1 = nullptr, *f2 = nullptr;
  184. split1(dp[v], f1, f2, res[i].first + 1);
  185. care[i] = _mx(f1);
  186. merge(dp[v], f1, f2);
  187. }
  188. int pf = 0;
  189. for (int i = 0; i < res.size(); ++i) {
  190. item *f1 = nullptr, *f2 = nullptr;
  191. split1(dp[v], f1, f2, res[i].first);
  192. if (f2) {
  193. int sh = max(res[i].second - pf, 0LL);
  194. f2->add += sh;
  195. f2->val += sh;
  196. f2->mx += sh;
  197. }
  198. merge(dp[v], f1, f2);
  199. pf = max(pf, res[i].second);
  200. }
  201. for (int i = 0; i < res.size(); ++i) {
  202. insert(dp[v], {res[i].first, res[i].second + care[i]});
  203. }
  204. }
  205. }
  206. insert(dp[v], {a[v].d, nd});
  207. cout << v << ": ";
  208. print(dp[v]);
  209. cout << endl;
  210. return;
  211. }
  212.  
  213. signed main() {
  214. srand(time(0));
  215. accell();
  216. cin >> n >> m >> k;
  217. for (int i = 1; i < n; ++i) {
  218. int p;
  219. cin >> p;
  220. --p;
  221. g[i].push_back(p);
  222. g[p].push_back(i);
  223. }
  224. for (int i = 0; i < m; ++i) {
  225. int v, d, w;
  226. cin >> v >> d >> w;
  227. --v;
  228. a[v].d = d;
  229. a[v].w = w;
  230. }
  231. dfs(0);
  232. cout << _mx(dp[0]);
  233. return 0;
  234. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement