题解 P4577 [FJOI2018]领导集团问题

题解区好像没有线段树上又套了二分的做法，于是就有了这片题解。

题目传送门

怀着必 WA 的决心交了两发，一不小心就过了。

求一个树上最长不下降子序列。

首先考虑裸的 dp：设 \(f_{u,j}\) 表示以 \(u\) 为根的子树里选的数的最大值不小于 \(j\) 能选多少个。

\[f_{u,j}=
\begin{cases}
\sum_\limits{v\ is\ u's\ son}f_{v,j} &j>w_u\\
\max\{\sum_\limits{v\ is\ u's\ son}f_{v,j},\sum_\limits{v\ is\ u's\ son}f_{v,j+1}+1\} &j\le w_u
\end{cases}
\]

接下来是如何优化：

在 DFS 每个节点的过程中，用权值线段树维护 \(f_{u,j}\)。

首先把所有儿子的权值线段树和起来。

然后考虑在什么区间选上这个节点更优。

右端点肯定是 \(w_i\) ，那么我们二分求左端点，即二分一个最小的选了比不选更优的点。

单点查询用权值线段树，合并儿子们的树用线段树合并，区间修改用标记可持久化。

时间复杂度是 \(O(nlog^2n)\)。

虽然慢到起飞但是能过。

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=a;i<=b;++i)
#define for_(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
#define bdmd int mid=(l+r)>>1
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f;
int n,cnt,w[N];
vector<int>son[N];
inline int rnt(){
    int x=0,w=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*w;
}
namespace LISAN{
    int ls[N];
    void LiSan(){
        _for(i,1,n){
            ls[i]=w[i];
        }
        sort(ls+1,ls+n+1);
        cnt=unique(ls+1,ls+n+1)-ls-1;
        _for(i,1,n)
            w[i]=lower_bound(ls+1,ls+cnt+1,w[i])-ls;
        return;
    }
}
class ValSegmentTree{
 public:
    int root[N],tot,uucnt,un_use[N*40];
    class TREE{
     public:
        int left_son,right_son;
        int val=0;
    }tree[N*40];
    const TREE NONE=(TREE){0,0,0};
    #define ls(p) tree[p].left_son
    #define rs(p) tree[p].right_son
    #define l_s(p) tree[p].left_son,l,mid
    #define r_s(p) tree[p].right_son,mid+1,r
    #define va(p) tree[p].val
    #define bdmd int mid=(l+r)>>1
    inline int NewP(){
        if(uucnt)
            return un_use[uucnt--];
        return ++tot;
    }
    inline void DeleteP(int p){
        tree[p]=NONE;
        un_use[++uucnt]=p;
        return;
    }
    void UpdateQJ(int &p,int l,int r,int le,int ri,int val){
        if(!p)p=NewP();
        if(ri<l||r<le)return;
        if(le<=l&&r<=ri)
            va(p)+=val;
        else{
            bdmd;
            UpdateQJ(l_s(p),le,ri,val);
            UpdateQJ(r_s(p),le,ri,val);
        }
    }
    int QueryP(int p,int l,int r,int x){
        if(!p)return 0;
        if(l==r)return va(p);
        else{
            bdmd;
            if(x<=mid)
                return va(p)+QueryP(l_s(p),x);
            else
                return va(p)+QueryP(r_s(p),x);
        }
    }
    void Merge(int &p1,int p2){
        if(!p1){p1=p2;return;}
        if(!p2){return;}
        va(p1)+=va(p2);
        Merge(ls(p1),ls(p2));
        Merge(rs(p1),rs(p2));
        DeleteP(p2);
        return;
    }
    #undef ls
    #undef rs
    #undef l_s
    #undef r_s
    #undef va
}tr;
void Dfs(int u,int father){
    int sz=son[u].size();
    _for(i,0,sz-1){
        int v=son[u][i];
        if(v==father)continue;
        Dfs(v,u);
        tr.Merge(tr.root[u],tr.root[v]);
    }
    int xuan=tr.QueryP(tr.root[u],1,cnt,w[u]+1)+1;
    int l=1,r=w[u];
    while(l<=r){
        bdmd;
        if(tr.QueryP(tr.root[u],1,cnt,mid)>=xuan)
            l=mid+1;
        else
            r=mid-1;
    }
    tr.UpdateQJ(tr.root[u],1,cnt,l,w[u],1);
    return;
}
int main(){
    n=rnt();
    _for(i,1,n)w[i]=rnt();
    LISAN::LiSan();
    _for(i,2,n){
        int x=rnt();
        son[i].push_back(x);
        son[x].push_back(i);
    }
    Dfs(1,0);
    printf("%d\n",tr.QueryP(tr.root[1],1,n,1));
    return 0;
}