Submission #467882

#	Time	Username	Problem	Language	Result	Execution time	Memory
467882		warner1129	Magic Tree (CEOI19_magictree)	C++17	100 / 100	207 ms	45868 KiB

magictree

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

struct segment_tree {
	static const int maxn = 2e6 + 5;
	int ls[maxn] = {}, rs[maxn] = {};
	long long ma[maxn] = {}, tag[maxn] = {};
	int buf = 0;
	inline void updata(int p, long long v) { ma[p] += v, tag[p] += v; }
	inline void pull(int p) { ma[p] = max(ma[ls[p]], ma[rs[p]]); }
	inline void push(int p) {
		if (!tag[p] || !p) return;
		if (ls[p]) updata(ls[p], tag[p]);
		if (rs[p]) updata(rs[p], tag[p]);
		tag[p] = 0;
	}
	void add(int &p, int l, int r, int pos, long long val, long long m) {
		if (!p) p = ++buf;
		if (l == r) { ma[p] = val + max(m, ma[p]); return; }
		push(p);
		int mid = (l + r) >> 1;
		if (pos <= mid) add(ls[p], l, mid, pos, val, m);	
		else add(rs[p], mid+1, r, pos, val, max(m, ma[ls[p]]));
		pull(p);
	}
	void Merge(int &a, const int &b, int l, int r, long long am, long long bm) {
		if (!b) { if (a) updata(a, bm); return; } 
		if (!a) { updata(b, am); a = b; return; }
		if (l == r) {
			am = max(am, ma[a]), bm = max(bm, ma[b]);
			ma[a] = max(ma[a] + bm, am + ma[b]);
			return;
		}
		int mid = (l + r) >> 1;
		push(a), push(b);
		Merge(rs[a], rs[b], mid+1, r, max(am, ma[ls[a]]), max(bm, ma[ls[b]]));
		Merge(ls[a], ls[b], l, mid, am, bm);
		pull(a);
	}
} seg;

const int maxn = 1e5 + 5;

vector<int> G[maxn];
pair<int, long long> fru[maxn];
int rt[maxn], d;

void dfs(int u) {
	for (int v : G[u])
		dfs(v), seg.Merge(rt[u], rt[v], 1, d, 0, 0);
	if (fru[u].ff) seg.add(rt[u], 1, d, fru[u].ff, fru[u].ss, 0);
}

void solve() {
	int n, m;
	cin >> n >> m >> d;
	for (int i = 2, f; i <= n; i++)
		cin >> f, G[f].emplace_back(i);
	for (int i = 1; i <= m; i++) {
		int id, d; long long w;
		cin >> id >> d >> w;
		fru[id] = {d, w};
	}
	dfs(1);
	cout << seg.ma[rt[1]] << '\n';
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17