Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*#pragma GCC optimize("Ofast,no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("fast-math")*/
- #include<bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using ull = unsigned long long;
- #define int long long
- // #define double ld
- #define F first
- #define S second
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- void accell() {
- cin.tie(0);
- cout.tie(0);
- ios_base::sync_with_stdio(0);
- }
- int n, m, k;
- const int N = 2e5;
- struct MM {
- int d = 0, w = 0;
- };
- struct item {
- item *l, *r;
- int cnt;
- int pr;
- int mx;
- int add;
- int val;
- int d;
- item (int key, int nk) {
- mx = key;
- d = nk;
- val = key;
- add = 0;
- pr = rand();
- cnt = 1;
- l = r = nullptr;
- }
- item () {
- l = r = nullptr;
- pr = rand();
- val = d = mx = cnt = add = 0;
- }
- };
- int _cnt(item *it) {
- return it ? it->cnt : 0;
- }
- int _mx(item *it) {
- return it ? it->mx : 0;
- }
- void upd_cnt(item *it) {
- if (it) {
- it->cnt = _cnt(it->l) + _cnt(it->r) + 1;
- it->mx = max(_mx(it->l), _mx(it->r));
- it->mx = max(it->val, it->mx);
- }
- }
- void push(item *it) {
- if (!it) return;
- if (it->l) it->l->add += it->add, it->l->val += it->add, it->l->mx += it->add;
- if (it->r) it->r->add += it->add, it->r->val += it->add, it->r->mx += it->add;
- it->add = 0;
- }
- void merge(item *&it, item *l, item *r) {
- push(l);
- push(r);
- if (!l || !r)
- it = l ? l : r;
- else if (l->pr > r->pr)
- merge(l->r, l->r, r), it = l;
- else
- merge(r->l, l, r->l), it = r;
- upd_cnt(it);
- }
- void split(item *it, item *&l, item *&r, int key, int add = 0) {
- if (!it) {
- l = r = nullptr;
- return;
- }
- push(it);
- int ck = _cnt(it->l) + add;
- if (key <= ck)
- split(it->l, l, it->l, key, add), r = it;
- else
- split(it->r, it->r, r, key, add + _cnt(it->l) + 1), l = it;
- upd_cnt(it);
- }
- void split1(item *it, item *&l, item *&r, int key) {
- if (!it) {
- l = r = nullptr;
- return;
- }
- push(it);
- int ck = it->d;
- if (key <= ck)
- split1(it->l, l, it->l, key), r = it;
- else
- split1(it->r, it->r, r, key), l = it;
- upd_cnt(it);
- }
- void out(item *it, vector<pair<int, int> >&x) {
- if (!it)
- return;
- push(it);
- out(it->l, x);
- x.push_back({it->d, it->val});
- out(it->r, x);
- }
- map<int, int>mp[N];
- item *dp[N];
- vector<int>g[N];
- MM a[N];
- void insert(item *it, pair<int, int>x) {
- item *f1 = nullptr, *f2 = nullptr;
- split1(it, f1, f2, x.first);
- merge(it, f1, new item(x.second, x.first));
- merge(it, it, f2);
- }
- void print(item *it) {
- if (!it)
- return;
- push(it);
- print(it->l);
- cout << it->d << ' ' << it->val << endl;
- print(it->r);
- }
- void dfs(int v, int p = -1) {
- dp[v] = new item(0, 0);
- int cur = v;
- for (int to : g[v]) {
- if (to != p) {
- dfs(to, v);
- if (_cnt(dp[to]) > _cnt(dp[cur])) {
- cur = to;
- }
- }
- }
- int nd = a[v].w;
- for (int to : g[v]) {
- if (to != p) {
- item *f1 = nullptr;
- item *f2 = nullptr;
- split(dp[to], f1, f2, a[v].d + 1);
- nd += _mx(f1);
- merge(dp[to], f1, f2);
- }
- }
- cout << endl;
- cout << a[v].d << ' ' << nd << ' ' << v << endl;
- swap(dp[v], dp[cur]);
- for (int to : g[v]) {
- if (to != p && to != cur) {
- vector<pair<int, int> > res;
- out(dp[to], res);
- vector<int>care((int)res.size());
- for (int i = 0; i < res.size(); ++i) {
- item *f1 = nullptr, *f2 = nullptr;
- split1(dp[v], f1, f2, res[i].first + 1);
- care[i] = _mx(f1);
- merge(dp[v], f1, f2);
- }
- int pf = 0;
- for (int i = 0; i < res.size(); ++i) {
- item *f1 = nullptr, *f2 = nullptr;
- split1(dp[v], f1, f2, res[i].first);
- if (f2) {
- int sh = max(res[i].second - pf, 0LL);
- f2->add += sh;
- f2->val += sh;
- f2->mx += sh;
- }
- merge(dp[v], f1, f2);
- pf = max(pf, res[i].second);
- }
- for (int i = 0; i < res.size(); ++i) {
- insert(dp[v], {res[i].first, res[i].second + care[i]});
- }
- }
- }
- insert(dp[v], {a[v].d, nd});
- cout << v << ": ";
- print(dp[v]);
- cout << endl;
- return;
- }
- signed main() {
- srand(time(0));
- accell();
- cin >> n >> m >> k;
- for (int i = 1; i < n; ++i) {
- int p;
- cin >> p;
- --p;
- g[i].push_back(p);
- g[p].push_back(i);
- }
- for (int i = 0; i < m; ++i) {
- int v, d, w;
- cin >> v >> d >> w;
- --v;
- a[v].d = d;
- a[v].w = w;
- }
- dfs(0);
- cout << _mx(dp[0]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement