BZOJ4919:大根堆

Description:

题目描述

给定一棵n个节点的有根树，编号依次为1到n，其中1号点为根节点。每个点有一个权值v_i。你需要将这棵树转化成一个大根堆。确切地说，你需要选择尽可能多的节点，满足大根堆的性质：对于任意两个点i,j，如果i在树上是j的祖先，那么v_i>v_j。请计算可选的最多的点数，注意这些点不必形成这棵树的一个连通子树。

输入格式

第一行包含一个正整数n(1<=n<=200000)，表示节点的个数。接下来n行，每行两个整数v_i,p_i(0<=v_i<=10^9,1<=p_i<i,p_1=0)，表示每个节点的权值与父亲。
输出格式
输出一行一个正整数，即最多的点数。

样例

样例输入

6
3 0
1 1
2 1
3 1
4 1
5 1

样例输出

思路：

我们可以先深搜到叶子，在叶子建树，然后直接向上合并到根，然后算出选或不选根节点的答案并比较，然后确定根节点要不要选，详见代码。

#include<bits/stdc++.h>

using namespace std;

namespace Decleration

{

    #define ll long long

    #define rr register

    const int SIZE=200004;

    int n,cnt;

    int v_[SIZE],v[SIZE];

    struct edge{int t,last;}a[SIZE];

    int last[SIZE];

    //快读

    static char buf[100000],*pa=buf,*pd=buf;

    #define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++

    inline int read()

    {

        register int x(0);register char c(gc);

        while(c<'0'||c>'9')c=gc;

        while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc;

        return x;

    }

    //建边

    inline void add(int f,int t)

    {

        a[++cnt].t=t;

        a[cnt].last=last[f];

        last[f]=cnt;

    }

    int cmp(const int a_cmp,const int b_cmp){return a_cmp<b_cmp;}

    //二分，离散化

}

using namespace Decleration;

namespace Line_Forest

{

    int num;

    int rt[SIZE],sum[SIZE*20];

    int lc[SIZE*20],rc[SIZE*20];

    //插入

    void updata(int &p,int L,int R,int l,int r,int z)

    {

        if(!p)

            p=++num;

        if(l<=L&&R<=r)

        {

            sum[p]+=z;

            return;

        }

        int mid=(L+R)>>1;

        if(l<=mid)

            updata(lc[p],L,mid,l,r,z);

        if(r>mid)

            updata(rc[p],mid+1,R,l,r,z);

    }

    //合并

    int merge(int p,int q,int l,int r)

    {

        if(!p)

            return q;

        if(!q)

            return p;

        sum[p]+=sum[q];

        int mid=(l+r)>>1;

        lc[p]=merge(lc[p],lc[q],l,mid);

        rc[p]=merge(rc[p],rc[q],mid+1,r);

        return p;

    }

    //查询小于等于val的个数

    int query(int p,int l,int r,int z)

    {

        if(!p)

            return 0;

        rr int mid=(l+r)>>1;

        rr int o=sum[p];

        if(z<=mid)

            o+=query(lc[p],l,mid,z);

        else

            o+=query(rc[p],mid+1,r,z);

        return o;

     }

    //深搜

    void dfs(int now)

    {

        for(rr int i=last[now];i!=-1;i=a[i].last)

        {

            dfs(a[i].t);

            rt[now]=merge(rt[now],rt[a[i].t],1,cnt);

        }

        rr int ans1=query(rt[now],1,cnt,v[now]-1)+1;

        rr int ans2=query(rt[now],1,cnt,v[now]);

        if(ans1<=ans2) return;

        int l=v[now],r=cnt,pos=v[now];

        //假如说根节点要选的话，可能面临着权值比自己大的的节点的可选节点数

        //比现有的最新的答案小，所以要二分一个满足这个条件的最大的区间，给这个区间加一

        //这实际上是向后更新

        //有DP那味了

        while(l<=r)

        {

            int mid=(l+r)>>1;

            if(query(rt[now],1,cnt,mid)<ans1)

            {

                l=mid+1;

                pos=mid;

            }

            else r=mid-1;

        }

        updata(rt[now],1,cnt,v[now],pos,1);

    }

};

using namespace Line_Forest;

int main()

{

    //freopen("1.in","r",stdin);

    //freopen("C.OUT","w",stdout);

    n=read();

    memset(last,-1,sizeof(last));

    for(rr int i=1;i<=n;i++)

    {

        v[i]=v_[i]=read();

        int fa=read();

        if(!fa) continue;

        add(fa,i);

    }

    sort(v_+1,v_+1+n,cmp);

    cnt=unique(v_+1,v_+1+n)-v_-1;

    for(rr int i=1;i<=n;i++)

        v[i]=lower_bound(v_+1,v_+1+cnt,v[i])-v_;

    dfs(1);

    printf("%d\n",query(rt[1],1,cnt,cnt));

    //fclose(stdout);

    //fclose(stdin);

}

这道题一开始交代码时TLE70后来将快读改成了更快的，并把register开满才过了，这里吐槽一下HZ的评测机，着实慢的一批啊。。。。。
另外蒟蒻有一个问题：板子与板子之间有区别吗？？同样是板子，为什么我一开始用下面的板子过不了然后换了个板子就过了。。。

        void insert(int &id,int l,int r,int val)

        {

            if(!id) id=++num;

            if(l==r)

            {

                sum[id]++;

                return;

            }

            int mid=(l+r)>>1;

            if(val<=mid) insert(lc[id],l,mid,val);

            else insert(rc[id],mid+1,r,val);

            sum[id]=sum[lc[id]]+sum[rc[id]];

        }

        int query_sum(int id,int l,int r,int val)

        {

            if(!id) return 0;

            if(l==r) return sum[id];

            int mid=(l+r)>>1;

            if(val<=mid) return query_sum(lc[id],l,mid,val);

            else return query_sum(rc[id],mid+1,r,val)+sum[lc[id]];

        }

        int merge(int id1,int id2,int l,int r)

        {

            if(!id1||!id2) return id1+id2;

            if(l==r)

            {

                sum[id1]+=sum[id2];

                return id1;

            }

            int mid=(l+r)>>1;

            lc[id1]=merge(lc[id1],lc[id2],l,mid);

            rc[id1]=merge(rc[id1],rc[id2],mid+1,r);

            sum[id1]=sum[lc[id1]]+sum[rc[id1]];

            return id1;

        }

请求路过的大神解释，蒟蒻能力有限，自己想不明白。。。。。

巴特西

2021-06-14 BZOJ4919:大根堆