bzoj2809: [Apio2012]dispatching

#include
#include
#include
#include
#include
#includeusing namespace std;
typedef long long LL;

int n;LL m;
LL c[210000],ld[210000];

struct node
{
    int x,y,next;
}a[210000];int len,last[210000];
void ins(int x,int y)
{
    len++;
    a[len].x=x;a[len].y=y;
    a[len].next=last[x];last[x]=len;
}


struct chairtree
{
    int lc,rc;
    LL c,sum;
}tr[4100000];int trlen,rt[210000];
int maketree(int now,int l,int r,LL k,LL s)
{
    if(now==0)now=++trlen;
    tr[now].c++, tr[now].sum+=s;
    if(lr)
    {
        int mid=(l+r)/2;
        if(kmaketree(tr[now].lc,l,mid,k,s);
        else       tr[now].rc=maketree(tr[now].rc,mid+1,r,k,s);
    }
    return now;
}
int merge(int x,int y)
{
    if(x==0||y==0)return x+y;
    tr[x].c+=tr[y].c;
    tr[x].sum+=tr[y].sum;
    tr[x].lc=merge(tr[x].lc,tr[y].lc);
    tr[x].rc=merge(tr[x].rc,tr[y].rc);
    return x;
}
LL tt[210000];
LL C,P;bool bk;
void getpeople(int x,int y,int l,int r)
{
    if(bk==false)return ;
    LL cc=tr[x].c-tr[y].c,sum=tr[x].sum-tr[y].sum;
    if(C+summ)
    {
        C+=sum, P+=cc;
        if(C+tt[l]>m)bk=false;
    }
    else if(l==r)
    {
        LL bi=min((m-C)/tt[l],cc);
        C+=bi*tt[l], P+=bi;
        if(bi==0)bk=false;
    }
    else 
    {
        int mid=(l+r)/2;
        getpeople(tr[x].lc,tr[y].lc,l,mid);
        getpeople(tr[x].rc,tr[y].rc,mid+1,r);
    }
}

LL erfen(LL k)
{
    int l=1,r=n,ret;
    while(lr)
    {
        int mid=(l+r)/2;
        if(tt[mid]k)
        {
            ret=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return ret;
}
int root,z,l[210000],r[210000];
void dfs(int x)
{
    l[x]=++z;
    rt[z]=maketree(rt[z],1,n,erfen(c[x]),c[x]);
    rt[z]=merge(rt[z],rt[z-1]);
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        dfs(y);
    }
    r[x]=z;
}

int main()
{
    int fa;
    scanf("%d%lld",&n,&m);
    for(int i=1;i)
    {
        scanf("%d%lld%lld",&fa,&c[i],&ld[i]);tt[i]=c[i];
        if(fa==0)root=i;
        else ins(fa,i);
    }
    sort(tt+1,tt+n+1);
    z=0;trlen=0;dfs(root);
    
    LL mmax=0;
    for(int i=1;i)
    {
        C=0;P=0;bk=true;
        getpeople(rt[r[i]],rt[l[i]-1],1,n);
        mmax=max(mmax,ld[i]*P);
    }
    printf("%lld\n",mmax);
    return 0;
}

#include
#include
#include
#include
using namespace std;
typedef long long LL;
int n,m;
struct node
{
    int x,y,next;
}a[1100000];int len,last[1100000];
struct heap
{
    int    l,r;
    LL c,d;
    heap()
    {
        l=r=d=0;
    }
}h[1100000];
int root[1100000];
void ins(int x,int y)
{
    len++;
    a[len].x=x;a[len].y=y;
    a[len].next=last[x];last[x]=len;
}
int Marge(int x,int y)
{
    if(x==0||y==0)return x+y;
    if(h[x].c//按工资维护大根堆，踢堆首维护花费小于m方便 
    h[x].r=Marge(h[x].r,y);
    if(h[h[x].l].dh[h[x].r].d)swap(h[x].l,h[x].r);
    h[x].d=h[h[x].r].d+1;
    return x;
}
LL p[1100000],s[1100000];//人数，花费钱数 
LL ans,ld[1100000];
void dfs(int x)//通过dfs序，使得每个点都成为一个大根堆，涵盖所有情况 
{
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        dfs(y);
        p[x]+=p[y];s[x]+=s[y];
        root[x]=Marge(root[x],root[y]);
    }
    while(s[x]>m)
    {
        s[x]-=h[root[x]].c;p[x]--;
        root[x]=Marge(h[root[x]].l,h[root[x]].r);
    }
    if(ld[x]*p[x]>ans)ans=ld[x]*p[x];
}
 
int main()
{
    int B;
    scanf("%d%d",&n,&m);
    for(int i=1;i)
    {
        scanf("%d%lld%lld",&B,&h[i].c,&ld[i]);
        ins(B,i);p[i]=1;s[i]=h[i].c;root[i]=i;
    }
    ans=0;dfs(1);
    printf("%lld\n",ans);
    return 0;
}