这道题好像有个名字：树上( ext{LIS})。
先考虑链上的情况。这个很经典：所要维护的信息(f_i)就是后缀中选取(i)个元素时，最前面元素的最大值。显然这个数组是递增的，数组大小就是答案（最多可选取(size)个元素）。加入(w)时二分找到刚好比(w)大的位置(pos)，则(pos+1)就可以被(pos)修改。
由此我们来考虑树上的情况：也就是将多条链合并起来。由于链与链之间互不影响，简单推一推发现，相当于将这些链上的元素合并再排序。最后再修改(pos+1)。( ext{set})或线段树合并都可以，后者复杂度更加优秀。
这个是用( ext{set})实现的。复杂度( ext{O}(nlog^2n))。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
#define ll long long
#define ull unsigned long long
#define rep(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define per(i, a, b) for (int i = a, i##end = b; i >= i##end; --i)
#define rep0(i, a) for (int i = 0, i##end = a; i < i##end; ++i)
#define per0(i, a) for (int i = a-1; ~i; --i)
#define chkmax(a, b) a = std::max(a, b)
#define chkmin(a, b) a = std::min(a, b)
inline int read() {
int w = 0, f = 1; char c;
while (!isdigit(c = getchar())) c == '-' && (f = -1);
while (isdigit(c)) w = w*10+(c^48), c = getchar();
return w * f;
}
const int maxn = 200000 + 5;
int n, val[maxn];
std::vector<int> G[maxn];
void adde(int u, int v) { G[u].push_back(v); }
std::multiset<int>::iterator it;
std::multiset<int> DFS(int u) {
std::multiset<int> ans;
rep0(i, G[u].size()) { // 启发式合并
std::multiset<int> nxt = DFS(G[u][i]);
if (ans.size() < nxt.size()) swap(ans, nxt);
for (it = nxt.begin(); it != nxt.end(); it++)
ans.insert(*it);
}
ans.insert(val[u]); // 以下稍微调整了操作：先插入，后删除。这样更方便
it = lower_bound(ans.begin(), ans.end(), val[u]);
if (it != ans.begin()) ans.erase(--it);
return ans;
}
int main() {
n = read();
rep(i, 1, n) val[i] = read();
rep(i, 2, n) adde(read(), i);
printf("%u", DFS(1).size()); // 答案显然为set大小
return 0;
}
这个是用线段树合并实现的。复杂度( ext{O}(nlog n))。实际效果仅仅比上面的快(dfrac{1}{2})。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define ll long long
#define ull unsigned long long
#define rep(i, a, b) for (int i = a, i##end = b; i <= i##end; ++i)
#define per(i, a, b) for (int i = a, i##end = b; i >= i##end; --i)
#define rep0(i, a) for (int i = 0, i##end = a; i < i##end; ++i)
#define per0(i, a) for (int i = a-1; ~i; --i)
#define chkmax(a, b) a = std::max(a, b)
#define chkmin(a, b) a = std::min(a, b)
inline int read() {
int w = 0, f = 1; char c;
while (!isdigit(c = getchar())) c == '-' && (f = -1);
while (isdigit(c)) w = w*10+(c^48), c = getchar();
return w * f;
}
const int maxn = 200000 + 5;
int n, val[maxn];
int lc[maxn<<6], rc[maxn<<6], sum[maxn<<6], rt[maxn], tot, flag;
void del(int o) {
if (o) sum[o]--, del(sum[rc[o]] ? rc[o] : lc[o]);
}
void modify(int &o, int l, int r, int p) { // 修改+删除前驱
if (!o) o = ++tot;
sum[o]++;
if (l == r) return;
int mid = l+r>>1;
if (mid < p) {
modify(rc[o], mid+1, r, p);
if (!flag && sum[lc[o]]) del(lc[o]), flag = 1; // 线段树最底下的分叉开始删除
} else modify(lc[o], l, mid, p);
if (flag) sum[o]--; // 分叉点往上都要删
}
void merge(int &u, int &v) { // 线段树合并。均摊起来单次logn
if (!u || !v) return void(u += v);
sum[u] += sum[v];
merge(lc[u], lc[v]), merge(rc[u], rc[v]);
}
std::vector<int> G[maxn];
void adde(int u, int v) { G[u].push_back(v); }
void dfs(int u) {
rep0(i, G[u].size()) dfs(G[u][i]), merge(rt[u], rt[G[u][i]]);
flag = 0, modify(rt[u], 1, 1e9, val[u]);
}
int main() {
n = read();
rep(i, 1, n) val[i] = read();
rep(i, 2, n) adde(read(), i);
dfs(1);
printf("%d", sum[rt[1]]);
return 0;
}