题意

树上 \(\text{LIS}\) 问题，要求树上最长不上升子序列。

思路

我们先回忆一下正常线性的 \(\text{LIS}\) 的方法，朴素做法是枚举前一位，复杂度是 \(O(n^2)\) 的。一个优化做法是（拿最长不上升子序列为例），对于一个新的值 \(k\)，我们找到它的前驱（小于它且最大的树），将其与前驱替换。这样在保证原有子序列有不上升性质的同时，还能保证当前的选择是最优的（可以理解成“紧凑”）。

举例说明一下，比如子序列 \(5,4,1\)，此时我们枚举到了 \(3\)，若将 \(1\) 替换成 \(3\)，子序列就成了 \(5,4,3\)，这样一来后续枚举到 \(2\) 时，还是可以并入这个子序列的，这就是我们查询前驱的目的所在了。

那么这些操作依然明了，且显然一个节点的子树们是互不影响的，于是我们考虑合并，最后剩余要插入的就是子树根节点的权值，之后的操作就是查询前驱和替换了。

实现

（1）\(\text{STL}\)

用一个 \(\text{multiset}\) 维护，并执行上述操作即可。

multiset s[maxn];
inline void merge(int x,int y){
	if(s[x].size()::iterator i=s[y].begin();i!=s[y].end();i++){
		s[x].insert(*i);
	}
}
inline void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		merge(u,v);
	}
	multiset::iterator i=s[u].lower_bound(w[u]);
	if(i!=s[u].end()) s[u].erase(i);
	s[u].insert(w[u]);
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
    	//这里为了方便查询前驱，赋值成负贡献
		w[i]=1e9-read();
	}
	for(int i=2;i<=n;i++){
		int v=read();
		add_edge(i,v);
		add_edge(v,i);
	}
	dfs(1,0);
	printf("%ld\n",s[1].size());
	return 0;
}

（2）线段树合并

离散化后用线段树去查前驱以及修改（注意特判本身为最小值的情况）。

int tot,rt[maxn];
struct SegmentTree{
	#define mid ((l+r)>>1)
	int ch[maxm][2],siz[maxm];
	bool pd=0;
	inline void merge(int &x,int &y){
		if(!x||!y){
			x+=y;
			return;
		}
		siz[x]+=siz[y];
		merge(ch[x][0],ch[y][0]),merge(ch[x][1],ch[y][1]);
	}
	inline void update(int x){
		if(!x) return;
		siz[x]--;
		if(siz[ch[x][1]]) update(ch[x][1]);
		else update(ch[x][0]);
	}
	inline void insert(int &x,int l,int r,int k){
		if(!x) x=++tot;
		siz[x]++;
		if(l==r) return;
		if(k<=mid){
			insert(ch[x][0],l,mid,k);
		}
		else{
			insert(ch[x][1],mid+1,r,k);
			if(!pd&&siz[ch[x][0]]){
				update(ch[x][0]);
				pd=1;
			}
		}
		if(pd) siz[x]--;
	}
}tree;
vector G;
inline int get(int x){
	return lower_bound(G.begin(),G.end(),x)-G.begin()+1;
}
inline void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		tree.merge(rt[u],rt[v]);
	}
	tree.pd=0;
	tree.insert(rt[u],1,G.size(),get(w[u]));
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		w[i]=read();
		G.push_back(w[i]);
	}
	sort(G.begin(),G.end());
	G.erase(unique(G.begin(),G.end()),G.end());
	for(int i=2;i<=n;i++){
		int v=read();
		add_edge(i,v);
		add_edge(v,i);
	}
	dfs(1,0);
	printf("%d\n",tree.siz[rt[1]]);
	return 0;
}