没有启发式合并的

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200'000;
int n;
vector<int> e[MAXN + 5];
int val[MAXN + 5];
// se[u]["i"] 表示子树 u 留下 i+1 个点的最大值最小是几
multiset<int> se[MAXN + 5];
void dfs(int u)
{
    for (int v : e[u])
    {
        dfs(v);
        // 把 se[v] 融入 se[u]
        for (auto x : se[v])
            se[u].insert(x);
    }
    auto it = se[u].lower_bound(val[u]);
    if (it != se[u].end())
        se[u].erase(it);
    se[u].insert(val[u]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int p;
        cin >> val[i] >> p;
        if (p != 0)
            e[p].push_back(i);
    }
    dfs(1);
    cout << se[1].size();
    return 0;
}

有启发式合并的

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200'000;
int n;
vector<int> e[MAXN + 5];
int val[MAXN + 5];
// se[u]["i"] 表示子树 u 留下 i+1 个点的最大值最小是几
multiset<int> se[MAXN + 5];
void dfs(int u)
{
    for (int v : e[u])
    {
        dfs(v);
        // 把 se[v] 融入 se[u]
        if (se[v].size() > se[u].size())
            swap(se[v], se[u]);
        for (auto x : se[v])
            se[u].insert(x);
        se[v].clear();
    }
    auto it = se[u].lower_bound(val[u]);
    if (it != se[u].end())
        se[u].erase(it);
    se[u].insert(val[u]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int p;
        cin >> val[i] >> p;
        if (p != 0)
            e[p].push_back(i);
    }
    dfs(1);
    cout << se[1].size();
    return 0;
}