P4577 [FJOI2018] 领导集团问题
大意
求树上最长不下降子序列。
思路
我们考虑从叶子向根去维护一条最长不上升子序列，我们试试用一个集合去维护目前的所选择的点，如果说我们想要选择更多的点，就需要尽可能使得下面选的点大，我们去寻找第一个大于等于\(now_v\) 的点，如果说找到的这个点要小于当前的 \(now_v\)，那么就可以替换掉。
我们采用启发式合并的思想，我们将小集合的向大集合进行插入，直接用 STL 的 multiset 维护，复杂度是 \(\mathcal{O}(n \log^2 n)\)。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 2 * 1e5 + 5;
vector<int> G[MAXN];
multiset<int> s[MAXN];
int v[MAXN];void dfs(int u){for(int son : G[u]){dfs(son);if(s[u].size() < s[son].size()){swap(s[u], s[son]);}for(int x : s[son]){s[u].insert(x);}s[son].clear();}auto it = s[u].lower_bound(v[u]);if(it != s[u].begin()){s[u].erase(-- it);}s[u].insert(v[u]);
}int n;int main(){
// freopen("heap.in", "r", stdin);
// freopen("heap.out", "w", stdout);ios::sync_with_stdio(0); cin.tie(0);cin >> n;for(int i = 1;i <= n;i ++){cin >> v[i];}for(int i = 2;i <= n;i ++){int f; cin >> f;G[f].push_back(i);}dfs(1);cout << s[1].size() << '\n';return 0;
}