改造二叉树

输入

3
2 2 2
1 0
1 1

输出

2

题解

先中序遍历
然后按a[i] - i 跑 最长不降子序列

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Tree
{
    int ch[2];
    int v;
} Node[100005];
int a[100005], Ind, val[100005], c[100005];
void dfs(int rt)
{
    if (rt)
    {
        dfs(Node[rt].ch[0]);
        a[++Ind] = Node[rt].v;
        dfs(Node[rt].ch[1]);
    }
}
int f[100005], Max[100005];
int tot;
inline int lowbit(int x) { return x & (-x); }
void Update(int x, int val)
{
    for (int i = x; i <= tot; i += lowbit(i))
        Max[i] = max(Max[i], val);
    return;
}
int Query(int x)
{
    int ans = 0;
    for (int i = x; i; i -= lowbit(i))
        ans = max(ans, Max[i]);
    return ans;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &Node[i].v);
    }
    int fa, d;
    for (int i = 2; i <= n; i++)
    {
        scanf("%d%d", &fa, &d);
        Node[fa].ch[d] = i;
    }
    dfs(1);
    //memset(f, 0x7f, sizeof(f));
    for (int i = 1; i <= n; i++)
    {
        a[i] = a[i] - i;
        c[i] = a[i];
    }
    int ans = 0;
    sort(a + 1, a + n + 1);
    tot = unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1; i <= n; i++)
    {
        int now = lower_bound(a + 1, a + tot + 1, c[i]) - a;
        f[i] = Query(now) + 1;
        Update(now, f[i]);
        ans = max(ans, f[i]);
    }
    printf("%d", n - ans);
    //while(1);
}