题解 T93279 【最长上升子树链】

传送门

30%的题解：

• 这棵树是一个链，所以直接做一遍LIS和LDS，经典DP算法，不多赘述。

60%的题解：

• $N<=1000$,可以直接$n^2$地做满分题解所说的DP。

满分题解：

• $F1[i]$表示以从以$i$为根节点的子树中出发，以$i$为结束点的LIS，同样设计一个$F2[i]$表示相同意思的LDS。

• 用动态开点的线段树维护，以权值为下标，记录$F1$、$F2$的值。

• 计算$u$节点的$F$值时，如果是计算$F1$,那么在子树中的$0 - (val[u]-1)$中找最大值，如果是计算$F2$，那么找$val[u] - inf$中的最大值。

• 答案就是找最大的$F1[u]+F2[u]-1$。注意子树的线段树最后要合并到父亲。时间复杂度$O(n \log n)$

// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>

#define inf 1000000000
#define MAXN 110000
using namespace std;
int n;

int val[MAXN];
int len, first[MAXN];
struct edge
{
    int v, next;
}e[MAXN * 2];

void ins(int u, int v)
{
    len++;
    e[len].v = v;
    e[len].next = first[u];
    first[u] = len;
}

int ans, L[MAXN * 60], R[MAXN * 60], t[MAXN * 60], cnt, root[MAXN][2];

void upd(int &u, int k, int c, int l, int r)
{
    if (u == 0)
	{
        u = ++cnt;
    }
    t[u] = max(t[u], c);
    if (l == r) return;
    int mid = (l + r) / 2;
    if (k <= mid) upd(L[u], k, c, l, mid);
        else upd(R[u], k, c, mid + 1, r);
}

int Find(int u, int fl, int fr, int l, int r)
{
    if (fl > fr) return 0;
    if (fl == l && fr == r) return t[u];
    if (u == 0) return 0;
    int mid = (l + r) / 2;
    if (fr <= mid) return Find(L[u], fl, fr, l, mid); else
    if (fl > mid)  return Find(R[u], fl, fr, mid + 1, r); else
    return max(Find(L[u], fl, mid, l, mid), Find(R[u], mid + 1, fr, mid + 1, r));
}

void merge(int &u1, int u2)
{
    if (u1 == 0)
	{
        u1 = u2;
        return;
    }
    if (u2 == 0) return;
    t[u1] = max(t[u1], t[u2]);
    merge(L[u1], L[u2]);
    merge(R[u1], R[u2]);
}

void dfs(int u)
{
    upd(root[u][0], val[u], 1, 0, 1000000000);
    upd(root[u][1], val[u], 1, 0, 1000000000);
    
    int in = 0, de = 0;
    
    for (int k = first[u]; k; k = e[k].next){
        int v = e[k].v;
        dfs(v);
            
        int f1 = Find(root[v][0], val[u] + 1, 1000000000, 0, 1000000000);
        int f2 = Find(root[v][1], 0, val[u] - 1, 0, 1000000000);
        
        in = max(in, f1);
        de = max(de, f2);
        
        merge(root[u][0], root[v][0]);
        merge(root[u][1], root[v][1]);
    }
    
    //cout << in << " " << de << endl;
    upd(root[u][0], val[u], in + 1, 0, 1000000000);
    upd(root[u][1], val[u], de + 1, 0, 1000000000);
    
    //cout << in << endl;
    ans = max(ans, in + de + 1);
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
	    int fa;
	    scanf("%d%d", &val[i], &fa);
	    if (fa) ins(fa, i);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}