自动搬运

查看原文

来自洛谷，原作者为

	LPF 看不懂黑白却听得到钟摆，去新世界冒险和内心作伴

搬运于2025-08-24 22:24:33，当前版本为作者最后更新于2021-07-21 22:15:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种别样的线段树合并写法。

$\mathcal Magic$

魔法树

给定一棵 $n$ 个节点的树，有些节点上有果实，有值 $d,w$，分别表示果实成熟的日期和价值。

如果恰好在日期当天切掉该节点与根的连通，那么就能得到该价值。求能得到的价值的最大值。

转化一下题意，在树上选择一些点，使得所有被选择的点对 $(u,v)$，若 $v$ 在以 $u$ 为根的子树中，那么有 $d(v)\leq d(u)$。

考虑最朴素的树形 DP，设 $f(u,i)$ 表示以 $u$ 为根的子树，所有切断操作都在 $\leq i$ 天内完成的最大价值。

那么对于 $u$ 的一个儿子 $v$，它的贡献有：

1. 不考虑加入 $u$ 点的价值：$f(u,i)=\sum f(v,i)$。
2. 考虑加入 $u$ 点的价值：$f(u,j)=w(u)+\sum f(v,d(u))$，其中 $j\geq d(u)$。

因为两者是互斥关系，所以需要取个 $\max$。

这样就得到了 $O(nk)$ 的暴力算法，考虑使用数据结构优化它，不难想到线段树合并。

对于转移一可以直接合并，打上个区间加标价即可，对于二相当于是区间 $[d(u),k]$ 对那个值取 $\max$。

然后提供一个小 trick，不考虑使用普通线段树的区间赋值标记（比较难合并），而是记录下区间 $\min,\max$。

如果一个区间的 $\min=\max$，那么这个区间所有值相等，这种情况下，

合并时直接被合并，更新时直接删掉左右儿子，修改时添加左右儿子，就相当于有了区间赋值的作用了。

时间复杂度 $O(n\log n)$，若写个空间回收那么空间复杂度同样为 $O(n\log n)$，可以参考下面的写法：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long LL;
const int N = 100010;
const int M = N * 40;

int n, m, k, tot, d[N], w[N], rt[N];
struct Tree{int l, r; LL mx, mn, add;} t[M];
vector<int> bac, G[N];

int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

bool Same(int p){return (t[p].mx == t[p].mn);}

int New(){
	if(!bac.empty()){
		int p = bac.back();
		bac.pop_back();
		return p;
	}
	return ++ tot;
}

void Delet(int &x){
	if(!x) return;
	bac.push_back(x);
	t[x].l = t[x].r = 0;
	t[x].mx = t[x].mn = t[x].add = 0;
	x = 0;
}

void Plus(int p, LL v){
	if(!p) return;
	t[p].mx += v;
	t[p].mn += v;
	t[p].add += v;
}

void Push_Down(int p){
	if(!t[p].add) return;
	Plus(t[p].l, t[p].add);
	Plus(t[p].r, t[p].add);
	t[p].add = 0;
}

void Push_Up(int p){
	int l = t[p].l, r = t[p].r;
	t[p].mx = max(t[l].mx, t[r].mx);
	t[p].mn = min(t[l].mn, t[r].mn);
	if(t[p].mn == t[p].mx)
		Delet(t[p].l), Delet(t[p].r);
}

int Merge(int p, int q){
	if(!p || !q) return p + q;
	if(Same(q)){Plus(p, t[q].mx); return p;}
	if(Same(p)){Plus(q, t[p].mx); return q;}
	Push_Down(p), Push_Down(q);
	t[p].l = Merge(t[p].l, t[q].l);
	t[p].r = Merge(t[p].r, t[q].r);
	Push_Up(p);
	return p;
}

LL Query(int p, int l, int r, int k){
	if(Same(p)) return t[p].mx;
	int mid = (l + r) >> 1;
	Push_Down(p);
	if(k <= mid)
		return Query(t[p].l, l, mid, k);
	else
		return Query(t[p].r, mid + 1, r, k);
}

void Modify(int p, int l, int r, int L, int R, LL v){
	if(t[p].mn >= v) return;
	if(L <= l && r <= R && t[p].mx <= v){
		t[p].mx = t[p].mn = v; t[p].add = 0;
		Delet(t[p].l), Delet(t[p].r);
		return;
	}
	Push_Down(p);
	if(Same(p)){
		t[p].l = New(), t[p].r = New();
		int ls = t[p].l, rs = t[p].r;
		t[ls].mx = t[ls].mn = t[rs].mx = t[rs].mn = t[p].mx;
	}
	int mid = (l + r) >> 1;
	if(L <= mid)
		Modify(t[p].l, l, mid, L, R, v);
	if(R > mid)
		Modify(t[p].r, mid + 1, r, L, R, v);
	Push_Up(p);
}

void dfs(int u){
	rt[u] = New();
	for(int i = 0; i < (int) G[u].size(); i ++){
		int v = G[u][i];
		dfs(v);
		rt[u] = Merge(rt[u], rt[v]);
	}
	if(d[u]){
		LL val = Query(rt[u], 1, k, d[u]);
		Modify(rt[u], 1, k, d[u], k, val + w[u]);
	}
}

int main(){
	n = read(), m = read(), k = read();
	for(int v = 2; v <= n; v ++){
		int u = read();
		G[u].push_back(v);
	}
	for(int i = 1; i <= m; i ++){
		int p = read();
		d[p] = read(), w[p] = read();
	}
	dfs(1);
	printf("%lld\n", t[rt[1]].mx);
	return 0;
}