不过下面这种方法不用线段树合并，只需要用multiset。

首先，我们先考虑一个序列的最长上升子序列。假设已经求出了前 i i i个数的最长上升子序列，在加入第 i + 1 i+1 i+1个数时，在当前数列中找到第一个大于等于它的数。如果有，则用新加入的数替换；否则将新加入的数放在队尾。

树上呢？也一样。对于每个节点，先遍历其子树，然后将该节点的儿子节点的最长上升子序列合并到自己的序列上。最后，在自己的序列上找到第一个大于等于该节点的权值的位置。如果有，将其在序列上删去，再把该节点的权值加在序列中；否则直接把该节点权值加在序列中。

这样做的话，每个节点都最多需要 O(n) 的时间复杂度来合并，看起来是 O(n^2) 的，但是我们可以用一种特殊的方法来保证其时间复杂度为 O(nlogn)。

我们将每个点的各个儿子中子树的节点数量最多的儿子称为重儿子（重子），其余为轻儿子（轻子）。重儿子与父亲的连边称为重边，其余边称为轻边，重边连成的链称为重链。那么每次先遍历重儿子，再将当前节点的multiset序列和其重儿子的multiset序列互换。也就是说，重链上的点在重链中只会被放入序列一次（因为重儿子的序列会被当前节点直接使用，避免重复合并）。

在这种情况下，我们考虑每个点被放入序列了多少次。每个点到根节点的路径上最多只会有 log n 条轻边（每从轻儿子沿轻边向上，子树大小至少为原来的两倍，因此轻边数量不超过 log n），那么，每个点总共只会被加 O(logn) 次，所有节点总共最多会被加入序列 O(nlogn) 次。而处理一条重边的时间复杂度为 O(1)，所以处理所有重边的总时间复杂度为 O(n)。

最后，根节点的序列的长度就是答案。因为可能有权值相等的节点，所以要用multiset而不能用set（set不允许重复元素，而multiset允许）。因为用了multiset，所以时间复杂度为 O(n log^2 n)。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,tot=0,a[N],siz[N],son[N];
vector<int> G[N];
multiset<int>s[N];

void dfs1(int x)
{
	siz[x]=1;son[x]=0;
	for(int y:G[x])
	{
		dfs1(y);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]]) son[x]=y;
	}
}
void dfs2(int x)
{
	multiset<int>::iterator it;
	if(son[x])
	{
		dfs2(son[x]);
		swap(s[x],s[son[x]]);
	}
	for(int y:G[x])if(y!=son[x]) 
	{
		dfs2(y);
		for(it=s[y].begin();it!=s[y].end();++it)s[x].insert(*it);
		s[y].clear();
	}
	it=s[x].lower_bound(a[x]);
	if(it!=s[x].end()) s[x].erase(it);
	s[x].insert(a[x]);
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)scanf("%d%d",&a[i],&x),G[x].push_back(i);
	dfs1(1);
	dfs2(1);
	printf("%d",s[1].size());
	return 0;
}

/*
不过下面这种方法不用线段树合并，只需要用multiset。

首先，我们先考虑一个序列的最长上升子序列。假设已经求出了前 i i i个数的最长上升子序列，
在加入第 i + 1 i+1 i+1个数时，在当前数列中找到第一个大于等于它的数。
如果有，则用新加入的数替换；否则将新加入的数放在队尾。

树上呢？也一样。对于每个节点，先遍历其子树，然后将该节点的儿子节点的最长上升子序列合并到自己的序列上。
最后，在自己的序列上找到第一个大于等于该节点的权值的位置。
如果有，将其在序列上删去，再把该节点的权值加在序列中；否则直接把该节点权值加在序列中。

这样做的话，每个节点都最多需要 O(n) 的时间复杂度来合并，看起来是 O(n^2) 的，但是我们
可以用一种特殊的方法来保证其时间复杂度为 O(nlogn)。

我们将每个点的各个儿子中子树的节点数量最多的儿子称为重儿子，其余为轻儿子。
重儿子与父亲的连边称为重边，其余边称为轻边，重边连成的链称为重链。
那么每次先遍历重儿子，再将当前节点的multiset序列和其重儿子的multiset序列互换。
也就是说，重链上的点在重链中只会被放入序列一次。
在这种情况下，我们考虑每个点被放入序列了多少次。
每个点到根节点的路径上最多只会有 log n 条轻边（每从轻儿子沿轻边向上，子树大小至少为原来的两倍），
那么，每个点总共只会被加 O(logn)次，所有节点总共最多会被加入序列  O(nlogn)次。
而处理一条重边的时间复杂度为 O ( 1 ) O(1) O(1)，
所以处理所有重边的总时间复杂度为 O ( n ) O(n) O(n)。

最后，根节点的序列的长度就是答案。因为可能有权值相等的节点，
所以要用multiset而不能用set。因为用了multiset，
所以时间复杂度为 O(n log^2 n)。
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,tot=0,a[N],siz[N],son[N];
vector<int> G[N];
multiset<int>s[N];

void dfs1(int x)
{
	siz[x]=1;son[x]=0;
	for(int y:G[x])
	{
		dfs1(y);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]]) son[x]=y;
	}
}
void dfs2(int x)
{
	multiset<int>::iterator it;
	if(son[x])
	{
		dfs2(son[x]);
		swap(s[x],s[son[x]]);
	}
	for(int y:G[x])if(y!=son[x]) 
	{
		dfs2(y);
		for(it=s[y].begin();it!=s[y].end();++it)s[x].insert(*it);
		s[y].clear();
	}
	it=s[x].lower_bound(a[x]);
	if(it!=s[x].end()) s[x].erase(it);
	s[x].insert(a[x]);
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)scanf("%d%d",&a[i],&x),G[x].push_back(i);
	dfs1(1);
	dfs2(1);
	printf("%d",s[1].size());
	return 0;
}