LibreOJ 2521 「FJOI2018」领导集团问题

首先将权值离散化。
不难想到设 fu,i 表示以 u 为根的子树内，最小值为 i 的最大集合大小（不一定要选 u）。
特别地，若集合为空，i=n+1。

那么对于 u 和其儿子 v，容易合并状态 f′u,i=max[n+1maxj=i(fu,i+fv,j),n+1maxj=i(fu,j+fv,i)]

线段树合并维护即可。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5;
int n;
int a[N + 5],ind[N + 5],len;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
namespace SEG
{
    struct node
    {
        int val,tag;
        int ls,rs;
    } seg[(N << 5) + 5];
    inline void push(int p)
    {
        if(seg[p].tag)
        {
            if(seg[p].ls)
                seg[seg[p].ls].val += seg[p].tag,
                seg[seg[p].ls].tag += seg[p].tag;
            if(seg[p].rs)
                seg[seg[p].rs].val += seg[p].tag,
                seg[seg[p].rs].tag += seg[p].tag;
            seg[p].tag = 0;
        }
    }
    void insert(int x,int k,int &p,int tl,int tr)
    {
        static int tot = 0;
        !p && (seg[p = ++tot] = seg[0],1),seg[p].val = max(seg[p].val,k);
        if(tl == tr)
            return ;
        push(p);
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
    }
    int query(int l,int p,int tl,int tr)
    {
        if(!p || l <= tl)
            return seg[p].val;
        push(p);
        int mid = tl + tr >> 1;
        int ret = -0x3f3f3f3f;
        l <= mid && (ret = max(ret,query(l,seg[p].ls,tl,mid)));
        ret = max(ret,query(l,seg[p].rs,mid + 1,tr));
        return ret;
    }
    int merge(int p,int q,int ptag,int qtag,int tl,int tr)
    {
        if(!p && !q)
            return 0;
        if(!p)
        {
            seg[q].val += qtag,seg[q].tag += qtag;
            return q;
        }
        if(!q)
        {
            seg[p].val += ptag,seg[p].tag += ptag;
            return p;
        }
        if(tl == tr)
        {
            ptag = max(ptag,seg[q].val),qtag = max(qtag,seg[p].val);
            seg[p].val = max(seg[p].val + ptag,seg[q].val + qtag);
            return p;
        }
        push(p),push(q);
        int mid = tl + tr >> 1;
        int prval = seg[seg[p].rs].val;
        int qrval = seg[seg[q].rs].val;
        seg[p].ls = merge(seg[p].ls,seg[q].ls,max(ptag,qrval),max(qtag,prval),tl,mid);
        seg[p].rs = merge(seg[p].rs,seg[q].rs,ptag,qtag,mid + 1,tr);
        seg[p].val = max(seg[seg[p].ls].val,seg[seg[p].rs].val);
        return p;
    }
}
int fa[N + 5];
int rt[N + 5];
void dfs(int p)
{
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
            fa[to[i]] = p,
            dfs(to[i]),
            rt[p] = SEG::merge(rt[p],rt[to[i]],0,0,1,len);
    SEG::insert(a[p],1 + max(SEG::query(a[p],rt[p],1,len),0),rt[p],1,len);
}
int main()
{
    SEG::seg[0].val = -0x3f3f3f3f;
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),ind[i] = a[i];
    sort(ind + 1,ind + n + 1),len = unique(ind + 1,ind + n + 1) - ind - 1;
    for(register int i = 1;i <= n;++i)
        a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind;
    int u;
    for(register int i = 2;i <= n;++i)
        scanf("%d",&u),add(u,i);
    dfs(1);
    printf("%d\n",SEG::seg[rt[1]].val);
}