题解 P4577 【[FJOI2018]领导集团问题】
dodo
2019-03-28 15:23:04
楼上两篇题解写的有一点点复杂,有map还写了离散化……
差分固然是一种理解方式,但其实有一种更好的理解方法和更简洁的代码。
那么现在我就来讲一讲
### 题意简述
文字语言:求树上最大权值随祖孙关系不降的点集大小
数学语言:求 $|S_{max}|$ 使得 $\forall{i,j(ancestor\ of \ i)\in S}, w_i\leq w_j$
为了方便描述,我们定义这种集合为“树上LIS”。
### 题解
考虑采用数学归纳法
类似处理序列LIS问题,对于每一个点 $u$ 使用multiset维护一个集合 $f_u$ 满足以下性质
- $f_{u,i}$ 表示在 $u$ 的子树中选择 $i$ 个点组成的所有树上LIS中,级别值 $w$ 最小值最大的那一个。
- 以 $u$ 为根节点的 $ans_u=|f_u|$($|f_u|$表示集合 $f_u$ 的大小)(该性质可由上述性质发现)
对于任意一个叶子节点 $u$, $f_u$显然只含有 $w_u$,满足树上LIS性质。
再考虑不是叶子节点的 $u$
假设点 $u$ 的所有孩子 $v$ 的 $f_v$ 已经满足求出并满足上述性质,我们应该如何求出 $u$ 的 $f_u$ 呢?
首先,显然 $u$ 的所有孩子不会相互影响,要从以 $u$ 为根节点的子树(除 $u$ )中选出大小为 $i$ 的树上LIS,可以直接贪心地选所有孩子集合中最大的 $i$ 个,于是只需将全部 $f_v$ 取并集并排序即可,于是可以直接将孩子们的 $f_v$ 集合全部启发式合并丢入 $f_u$ 的multiset ,记 $S=\bigcup_{v\in u.son}f_v$
现在我们考虑将 $u$ 加入 $S$ 集合并使集合满足性质
我们直接在multiset上二分出第一个 $i$ 满足 $f_{u,i}\geq w_u$ 那么我们将 $u$ 接在 $i$ 前显然是最优方案,此时 $f_{u,i-1}$ 就可以被 $w_u$ 替换,那么现在的集合就是我们要求的 $f_u$,并且满足树上LIS性质。
按照这样的方式在树上dfs即可求出 $f_1$,此时答案即为 $|f_1|$。
### 复杂度证明
该算法的复杂度为 $O(nlog^2n)$
考虑同样采用数学归纳法
记 $T_u$ 表示处理出 $f_u$ 的时间复杂度,$S_u$表示 $u$ 的子树大小
我们需要证明 $T_u=S_ulog^2S_u$
对于任意一个叶子节点 $u$,$S_u=1$,此时只需在multiset中插入 $w_u$ 复杂度为 $O(1)$,满足$T_i=S_ulog^2S_u$
再考虑不是叶子节点的 $u$
假设点 $u$ 的所有孩子 $v$ 的 $T_v=S_vlog^2S_v$
那么 $T_i=\sum_{v\in u.son}T_v+T_{merge}$
因为子孙们包含的节点个数$\sum_{v\in u.son}S_v+1=S_u$
所以$\sum_{v\in u.son}T_v\leq S_ulog^2S_u$
启发式合并的复杂度为 $S_ulogS_u$,使用multiset维护加一个log,$T_{merge}=S_ulog^2S_u$
所以$T_u$与 $S_ulog^2S_u$ 同阶
证毕。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
multiset<int> f[N];
multiset<int>::iterator it;
int n, w[N], ans;
int h[N], to[N], nxt[N], t;
bool comp(int x, int y) { return w[x] < w[y]; }
void add(int u, int v) { to[++t] = v, nxt[t] = h[u], h[u] = t; }
void merge(int u, int v) {
if(f[u].size() < f[v].size()) swap(f[u], f[v]);
for(it = f[v].begin(); it != f[v].end(); ++it) f[u].insert(*it);
}
void dfs(int u) {
for(int i = h[u]; i; i = nxt[i]) dfs(to[i]), merge(u, to[i]);
f[u].insert(w[u]);
it = f[u].lower_bound(w[u]);
if(it != f[u].begin()) f[u].erase(--it);
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &w[i]);
for(int i = 2; i <= n; ++i) {
int f;
scanf("%d", &f);
add(f, i);
}
dfs(1);
printf("%d", f[1].size());
}
```