---

题目传送门

题目大意：给定一棵树，每个节点都有一个权 $w$。从中挑出几个节点，使得挑出的任意两个节点 $u,v$，若 $u$ 在树上为 $v$ 的祖先，那么要求满足 $w_u\le w_v$，即满足小根堆性质。

---

暴力思路

很显然是一道树形 $dp$。
设 $d{p}_{i,j}$ 表示：在以 $i$ 节点为根的子树上，选择权值大于等于 $j$ 的节点，最多能选几个。
那么就会得到以下代码：

void dfs(int u) {
	for (int v : e[u]) {
		dfs(v);
		// 由于 u 节点的【不同子树间】不会受到小根堆的性质影响
		// 所以直接累加即可
		for (int i = 1; i <= tot; ++i)  // tot 为离散化后有多少个不同的数
			dp[u][i] += dp[v][i];
	}
	// 由于要有 w[u] <= w[v], 所以在选择时, 子树所选节点权值必须大于等于 w[u]
	// 因此对于 i <= w[u-] 的部分, 要决策选或不选 u 节点
	// max 中的两个式子分别表示【不选节点 u】与 【选节点 u】的贡献
	for (int i = 1; i <= w[u]; ++i)
		dp[u][i] = max(dp[u][i], dp[u][w[u]] + 1);
}

时间复杂度是 $O(n\times tot)$ 的，空间是 $O(n^2)$。
完整代码如下 (当然你如果把它交到洛谷上会发现全 RE) ：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e3 + 7;

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

int n, w[maxn];
vector<int> e[maxn];

int dp[maxn][maxn];

int hush[maxn], tot;

void dfs(int u) {
	for (int v : e[u]) {
		dfs(v);
		for (int i = 1; i <= tot; ++i)  // 转移方程 1
			dp[u][i] += dp[v][i];
	}
	for (int i = 1; i <= w[u]; ++i)  // 转移方程 2
		dp[u][i] = max(dp[u][i], dp[u][w[u]] + 1);
}
int main() {
	n = read();
	for (int i = 1; i <= n; ++i)
		hush[i] = w[i] = read();
	for (int i = 1, f; i < n; ++i)
		f = read(), e[f].push_back(i + 1);
	sort(hush + 1, hush + n + 1);
	tot = unique(hush + 1, hush + n + 1) - hush - 1;
	dfs(1);
	printf("%d\n", dp[1][1]);
	return 0;
}

---

正解思路

观察 转移方程2 & 最后答案，需要区间修改 & 单点查询答案，我们用线段树；
观察 转移方程1，需要区间叠加，我们就用线段树合并。

具体如下：

1. 对于 $d{p}_{u,i}=\sum d{p}_{v,i},i\in [1,tot]$：我们直接使用 $merge$ 操作即可；
2. 对于 $d{p}_{u,i}=max(d{p}_{u,i},d{p}_{u,w_u}+1),i\in [1,w_u]$：
   我们可以发现，当 $u$ 不变时，随着 $i$ 的增加，它是非严格单调递减的（因为大于等于 $i$ 的数越来越少），因此我们可以在 $[1,w_u]$ 区间中二分出一个 $[l,w_u]$ 的区间，使得这个区间里的所有 $dp$ 值都小于 $d{p}_{u,w_u}+1$，此时再用线段树区间覆盖就好了。

本人尝试过 转移方程2 用区间覆盖来写，但怎么调都过不去为了更好地了解线段树，我特地看了题解，了解到标记永久化这个东西。

标记永久化就是不再用懒惰标记，当我们给一个区间加上一个值 $v$ 时（假设线段树上管理这个区间的节点时 $o$），那我们就直接在节点 $o$ 上加 $v$，然后查询某个单点时，把父链上所有的权值累加，就得到我们要查询的【单点】的值（有点像线段树上查分）。

当然这种操作仅限于【单点查询】。

于是乎，就得到了一个 $O(nlog(n))$ 的代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 2e5 + 7;

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

int n, w[maxn];
int h[maxn], ecnt;
struct edge {int v, nxt;} e[maxn];
void addedge(int u, int v) {e[++ecnt] = edge{v, h[u]}, h[u] = ecnt;}

int hush[maxn], tot;

int rt[maxn], nds;
struct node {
	int ls, rs, s;
} t[maxn * 30];
#define mid ((l + r) >> 1)
void mdf(int& o, int l, int r, int ql, int qr, int v) {
	if (qr < l || r < ql) return ;
	if (!o) o = ++nds;
	if (ql <= l && r <= qr) {t[o].s += v; return ;}
	mdf(t[o].ls, l, mid, ql, qr, v);
	mdf(t[o].rs, mid + 1, r, ql, qr, v);
}
int ask(int o, int l, int r, int q) {
	if (!o) return 0;
	if (q <= mid) return ask(t[o].ls, l, mid, q) + t[o].s;
	return ask(t[o].rs, mid + 1, r, q) + t[o].s;
}
int merge(int a, int b, int l, int r) {
	if (!a || !b) return a + b;
	t[a].s += t[b].s;
	if (l != r) {
		t[a].ls = merge(t[a].ls, t[b].ls, l, mid);
		t[a].rs = merge(t[a].rs, t[b].rs, mid + 1, r);
	}
	return a;
}
void dfs(int u) {
	for (int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].v; dfs(v);
		rt[u] = merge(rt[u], rt[v], 1, tot);
	}
	w[u] = lower_bound(hush + 1, hush + tot + 1, w[u]) - hush;
	int num = ask(rt[u], 1, tot, w[u]) + 1;  // 暴力中的 dp[u][w[u]] + 1
	
	// 二分找到 [1, w[u]] 中 dp[u][pos] < num 中的第一个 pos 
	int pos = 0;
	int l = 1, r = w[u];
	while (l <= r) {
		if (ask(rt[u], 1, tot, mid) < num)
			pos = mid, r = mid - 1;
		else l = mid + 1;
	}
	mdf(rt[u], 1, tot, pos, w[u], 1);
}
int main() {
	n = read();
	for (int i = 1; i <= n; ++i)
		hush[i] = w[i] = read();
	for (int i = 1, f; i < n; ++i)
		f = read(), addedge(f, i + 1);
	sort(hush + 1, hush + n + 1);
	tot = unique(hush + 1, hush + n + 1) - hush - 1;
	dfs(1);
	printf("%d\n", ask(rt[1], 1, tot, 1));
	return 0;
}

---

一个疑惑点

这里本人之前一直有一个疑惑点，有必要说一下，以免以后又忘了。
疑惑点在【选上 $u$ 节点的转移方程】上。

在二分时，我们假设找到的位置是 $pos$，当然 $pos\le w_u$。此时我们再给区间 $[pos,w_u]$ 加上 $1$（其实就是给原来暴力中的 $d{p}_{u,pos...w_u}$ 都加上了 $1$），是不是意味着对于某些 $d{p}_{u,x},x\in [pos,w_u)$，我们既选了 $u$ 节点，又选了子树中权值小于 $w_u$ 的节点 ?（这样显然就不满足小根堆性质了）

答案是否定的，因为以 $u$ 为根节点的子树中【权值在 $[pos,w_u)$ 的节点】是不存在的！

我们可以采用反证法证明：
我们假设子树中存在节点权值为 $pos$ 的节点，那么【节点权值为 $pos$】的【节点个数】是 $\ge 1$ 的。
那么 $d{p}_{u,pos}$ 的贡献由两部分组成：一部分是由权值 $\ge w_u$ 的节点贡献的，另一部分是由权值 $[pos,w_u)$ 的节点贡献的。
前者显然是 $d{p}_{u,w_u}$，后者显然是 $\ge 1$ 的，因此 $d{p}_{u,pos}\ge d{p}_{u,w_u}+1$，与所二分出的 $pos$ 是矛盾的。
因此以 $u$ 为根的子树中并不存在权值 $[pos,w_u)$ 的节点，所以算法的正确性没有问题。

---

相似的题

BZOJ 4919 大根堆