2809: [Apio2012]dispatching

Time Limit: 10 Sec Memory Limit: 128 MB

Submit: 1932 Solved: 967

[Submit][Status][Discuss]

Description

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后根据自己的工作获取报偿。在这个帮派里。有一名忍者被称之为 Master。除了 Master以外。每名忍者都有且仅有一个上级。为保密，同一时候增强忍者们的领导力。全部与他们工作相关的指令总是由上级发送给他的直接下属，而不同意通过其它的方式发送。

如今你要招募一批忍者，并把它们派遣给顾客。

你须要为每一个被派遣的忍者 支付一定的薪水，同一时候使得支付的薪水总额不超过你的预算。另外，为了发送指令，你须要选择一名忍者作为管理者，要求这个管理者能够向全部被派遣的忍者 发送指令。在发送指令时，不论什么忍者（无论是否被派遣）都能够作为消息的传递 人。管理者自己能够被派遣，也能够不被派遣。当然。假设管理者没有被排遣，就不须要支付管理者的薪水。你的目标是在预算内使顾客的惬意度最大。这里定义顾客的惬意度为派遣的忍者总数乘以管理者的领导力水平。当中每一个忍者的领导力水平也是一定的。写一个程序，给定每一个忍者 i的上级 Bi。薪水Ci，领导力L i，以及支付给忍者们的薪水总预算 M，输出在预算内满足上述要求时顾客惬意度的最大值。

1 ≤N ≤ 100,000 忍者的个数；

1 ≤M ≤ 1,000,000,000 薪水总预算；

0 ≤Bi < i 忍者的上级的编号；

1 ≤Ci ≤ M 忍者的薪水；

1 ≤Li ≤ 1,000,000,000 忍者的领导力水平。

Input

从标准输入读入数据。

第一行包括两个整数 N和 M，当中 N表示忍者的个数。M表示薪水的总预算。

接下来 N行描写叙述忍者们的上级、薪水以及领导力。

当中的第 i 行包括三个整 Bi , C i , L i分别表示第i个忍者的上级。薪水以及领导力。Master满足B i = 0，而且每一个忍者的老板的编号一定小于自己的编号 Bi < i。

Output

输出一个数。表示在预算内顾客的惬意度的最大值。

Sample Input

5 4

0 3 3

1 3 5

2 2 2

1 2 4

2 3 1

Sample Output

6

HINT

假设我们选择编号为 1的忍者作为管理者而且派遣第三个和第四个忍者，薪水总和为 4。没有超过总预算 4。由于派遣了 2 个忍者而且管理者的领导力为 3。

用户的惬意度为 2 。是能够得到的用户惬意度的最大值。

Source

这个题做法非常多,能够dfs序+主席树,能够平衡树启示式合并,能够左偏树

我写的Splay启示式合并

显然每次选择费用最小的当下属.

对每一个节点把他的孩子节点合并到他的平衡树上,对每一个节点记录一下子树费用和.

然后乱搞一下233

然而Codevs和BZOJ过了,COGS上单点时限0.4s就被卡掉了…

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define MAXN 100010

#define LL long long

using namespace std;

int n,m,top,temp;

LL maxn;

int root,que[MAXN];

int L[MAXN];

struct splay

{

    int ch[2],fa;//0左1右

    int size,data;

    LL sum;//子树费用和

}tree[MAXN];

struct edge

{

    int to;

    edge *next;

}e[MAXN],*prev[MAXN];

void in(int &x)

{

    char ch=getchar();x=0;

    while (!(ch>='0'&&ch<='9')) ch=getchar();

    while (ch>='0'&&ch<='9')    x=x*10+ch-'0',ch=getchar();

}

inline void add(int u,int v)

{

    e[++top].to=v;e[top].next=prev[u];prev[u]=&e[top];

}

inline void calc(int x)

{

    tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+1;

    tree[x].sum=tree[tree[x].ch[0]].sum+tree[tree[x].ch[1]].sum+tree[x].data;

}

inline void rot(int x,bool flag)//0左旋1右旋

{

    int y=tree[x].fa;

    tree[y].ch[!flag]=tree[x].ch[flag];

    if  (tree[x].ch[flag])  tree[tree[x].ch[flag]].fa=y;

    tree[x].fa=tree[y].fa;

    if  (tree[tree[y].fa].ch[0]==y) tree[tree[y].fa].ch[0]=x;

        else    tree[tree[y].fa].ch[1]=x;

    tree[x].ch[flag]=y;tree[y].fa=x;

    calc(x);calc(y);

}

inline void Splay(int x,int f)

{

    if (!x||x==f)   return;

    while   (tree[x].fa!=f)

    {

        if  (tree[tree[x].fa].fa==f)

        {

            if  (tree[tree[x].fa].ch[0]==x) rot(x,1);

            else    rot(x,0);

        }

        else

        {

            int y=tree[x].fa,z=tree[y].fa;

            if  (tree[z].ch[0]==y)

                if  (tree[y].ch[0]==x)  rot(y,1),rot(x,1);

                else    rot(x,0),rot(x,1);

            else

                if  (tree[y].ch[0]==x)  rot(x,1),rot(x,0);

                else    rot(y,0),rot(x,0);

        }

    }

    if  (x) calc(x);

    if  (f) calc(f);

}

inline void insert(int x,int node)

{

    int N=x,t=0;

    while   (N)

    {

        t=N;

        if  (tree[node].data>=tree[N].data) N=tree[N].ch[1];

        else    N=tree[N].ch[0];

    }

    tree[node].fa=t;

    if  (tree[node].data>=tree[t].data) tree[t].ch[1]=node;

    else    tree[t].ch[0]=node;

    Splay(node,0);

}

inline void insert(int &rt,int F,int x)

{

   if   (rt==0)

   {

       rt=x;

       tree[x].fa=F;

       Splay(x,0);

       return;

   }

   if   (tree[x].data<=tree[rt].data)   insert(tree[rt].ch[0],rt,x);

   else insert(tree[rt].ch[1],rt,x);

}

inline void Union(int x,int y)

{

    Splay(x,0);Splay(y,0);

    calc(x);calc(y);

    if  (tree[y].size>tree[x].size) swap(x,y);

    int head=0,tail=1;

    que[0]=x,que[1]=y;

    while   (head<tail)

    {

        int now=que[++head];

        if  (tree[now].ch[0])   que[++tail]=tree[now].ch[0];

        if  (tree[now].ch[1])   que[++tail]=tree[now].ch[1];

        tree[now].ch[0]=tree[now].ch[1]=0;

        insert(que[head-1],0,now);

    }

}

inline int rank(int data,int x)

{

    if  (!x)    return 0;

    if (data>=tree[x].sum)  return tree[x].size;

    if (data==tree[tree[x].ch[0]].sum+tree[x].data) return tree[tree[x].ch[0]].size+1;

    if (data<tree[tree[x].ch[0]].sum+tree[x].data) return rank(data,tree[x].ch[0]);

    return tree[tree[x].ch[0]].size+1+rank(data-tree[tree[x].ch[0]].sum-tree[x].data,tree[x].ch[1]);

}

inline void solve()

{

    for (int x=n;x;x--)

    {

        for (edge *i=prev[x];i;i=i->next)   Union(i->to,x);

        Splay(x,0);

        maxn=max(maxn,(long long)(rank(m,x))*L[x]);

    }

}

int main()

{

    scanf("%d%d",&n,&m);

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

    {

        int f,c;

        in(f);in(c);in(L[i]);

        if  (f==0)  root=i;

        else    add(f,i);

        tree[i].size=1;tree[i].sum=tree[i].data=c;

        tree[i].ch[0]=tree[i].ch[1]=tree[i].fa=0;

    }

    solve();

    cout<<maxn<<endl;

}