[FJOI2018]领导集团问题(树形dp+整体dp)

题目描述：

 这道题其实就是树上LIS

10pts的做法

40pts的做法

100pts的做法

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
    int pre, to;
}edge[400010];
int head[200010], tot;
int n, cnt;
int a[200010], b[200010];
int num, ls[4000010], rs[4000010], sum[4000010], rt[4000010];
void add(int &p, int l, int r, int pos, int val) {
    if (!p) p = ++num;
    if (l == r) {
        sum[p] += val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) add(ls[p], l, mid, pos, val);
    else add(rs[p], mid + 1, r, pos, val);
    sum[p] = sum[ls[p]] + sum[rs[p]];
}
int Find(int p, int l, int r, int pos) {
    if (!p) return 0;
    if (l == r) return sum[p] ? l : 0;
    int mid = (l + r) >> 1;
    if (pos <= mid) return Find(ls[p], l, mid, pos);
    else {
        int f = Find(rs[p], mid + 1, r, pos);
        if (f) return f;
        return Find(ls[p], l, mid, pos);
    }
}
int merge(int u, int v) {
    if (!v) return u;
    if (!u) return v;
    sum[u] += sum[v];
    ls[u] = merge(ls[u], ls[v]);
    rs[u] = merge(rs[u], rs[v]);
    return u;
}
void dfs(int x) {
    for (int i = head[x]; i; i = edge[i].pre) {
        dfs(edge[i].to);
        rt[x] = merge(rt[x], rt[edge[i].to]);
    }
    add(rt[x], 0, cnt, a[x], 1);
    int f = Find(rt[x], 0, cnt, a[x] - 1);
    if (f) add(rt[x], 0, cnt, f, -1);
}
void add(int u, int v) {
    edge[++tot] = node{head[u], v};
    head[u] = tot;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    cnt = n;
    sort(b + 1, b + cnt + 1);
    cnt = unique(b + 1, b + cnt + 1) - b - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
    for (int i = 2, x; i <= n; i++) {
        cin >> x;
        add(x, i);
    }
    dfs(1);
    cout << sum[rt[1]];
    return 0;
}