题目链接
题解
链上的(LIS)维护一个数组(f[i])表示长度为(i)的(LIS)最小的结尾大小
我们可以用(multiset)来维护这个数组，子树互不影响，启发式合并
一个点取更新数组时，只会改变第一个比它大的地方，因为这个点一定是将比它小的位置(+1)，只有(+1)后位置的值比它大才会产生贡献
所以找到第一个大于等于当前节点权值的位置，改为当前节点权值即可
复杂度(O(nlog^2n))
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 200005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
return flag ? out : -out;
}
int val[maxn],fa[maxn],ls[maxn],rb[maxn],n;
multiset<int> f[maxn];
void dfs(int u){
for (int k = ls[u]; k; k = rb[k]){
dfs(k);
if (f[k].size() > f[u].size()) swap(f[u],f[k]);
for (set<int>::iterator it = f[k].begin(); it != f[k].end(); it++)
f[u].insert(*it);
f[k].clear();
}
if (f[u].size() > 0 && f[u].lower_bound(val[u]) != f[u].end())
f[u].erase(f[u].lower_bound(val[u]));
f[u].insert(val[u]);
}
int main(){
n = read();
REP(i,n){
val[i] = read(); fa[i] = read();
rb[i] = ls[fa[i]]; ls[fa[i]] = i;
}
dfs(1);
printf("%d
",(int)f[1].size());
return 0;
}