题意简述
有一个以 \(1\) 为根的有根树，每个点有权值 \(v_i\)。你需要选出一个点集 \(S\)，使得点集里任意两个元素 \(x,y\)，若 \(x\) 在原树上是 \(y\) 的祖先，则要满足 \(v_x>v_y\)。求选出的点集的最大大小是多少。
解法
原题限制相当于：在选出的点集构成的新树 \(T\) 中，每个点到根节点上的点权形成上升子序列。要让点集大小最大，就是让上升子序列长度最大。
不会最长上升子序列的建议前往这里。
先说做法：对每个节点维护一个 set，合并子树的 set 时用启发式合并，插入元素时寻找第一个大于等于它本身的元素，删除原来的元素，并加入这个元素。若没有，直接加入。最终根节点的 set 大小就是答案。
代码略去缺省源。
点击查看代码
int n,m,a[maxn];
vector<int>G[maxn];
multiset<int>s[maxn];
void merge(multiset<int>&x,multiset<int>&y){
if(x.size()<y.size())swap(x,y);
while(!y.empty())x.insert(*y.begin()),y.erase(y.begin());
}
void dfs(int x){
for(int u:G[x]){
dfs(u);merge(s[x],s[u]);
}
auto it=s[x].lower_bound(a[x]);
if(it!=s[x].end())s[x].erase(it);
s[x].insert(a[x]);
}
void solve_the_problem(){
n=rd(),a[0]=inf;
rep(i,1,n){
int x;a[i]=rd(),x=rd();
G[x].pb(i);
}
dfs(1);
write(s[1].size());
}