BZOJ2809: [Apio2012]dispatching

题解:题意很复杂不知道他在说什么冷静想了一下后其实就是给你总数n的人每个人有一个领导值他能领导他的子树节点问以某个点为领导时他能最多派出忍者个数乘以领导值的最大值是多少 (每个人都有薪水总共派出的薪水的总和不得超出m)

/**************************************************************
    Problem: 2809
    User: c20161007
    Language: C++
    Result: Accepted
    Time:4960 ms
    Memory:9824 kb
****************************************************************/
 
#include <bits/stdc++.h>
#define ll long long
const int MAXN=1e5+10;
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
int ch[MAXN][2],pre[MAXN],f[MAXN],key[MAXN];
int size[MAXN];ll a[MAXN];
vector<int>vec[MAXN];
ll sum[MAXN];int cnt;
/*void Treavel(int x)
{
    if(x)
    {
        Treavel(ch[x][0]);
        printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,key=%2d
",x,ch[x][0],ch[x][1],pre[x],size[x],key[x]);
        Treavel(ch[x][1]);
    }
}
void debug(int rp)
{
    splay(rp);
    printf("root:%d
",rp);
    Treavel(rp);
}*/
void newnode(int &x,int y,int vul){
    size[x]=1;
    ch[x][0]=ch[x][1]=0;pre[x]=y;key[x]=sum[x]=vul;
}
void up(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+1;sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x];}
void rotate(int x,int kind){
    int y=pre[x];
    ch[y][!kind]=ch[x][kind];pre[ch[x][kind]]=y;
    if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];ch[x][kind]=y;pre[y]=x;
    up(y);
}
void splay(int x,int goal){
    while(pre[x]!=goal){
    if(pre[pre[x]]==goal)rotate(x,ch[pre[x]][0]==x);
    else{
        int y=pre[x];int kind=ch[pre[y]][0]==y;
        if(ch[y][kind]==x)rotate(x,!kind),rotate(x,kind);
        else rotate(y,kind),rotate(x,kind);
    }
    }
  //  if(goal==0)root=x;
    up(x);
}
void Treavel(int x)
{
    if(x)
    {
        Treavel(ch[x][0]);
        printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,sum=%2d
",x,ch[x][0],ch[x][1],pre[x],size[x],sum[x]);
        Treavel(ch[x][1]);
    }
}
void debug(int rp)
{
    splay(rp,0);
    printf("root:%d
",rp);
    Treavel(rp);
}
int st[MAXN],tot;
void dfs(int x){
    if(!x)return ;
    st[++tot]=x;
    dfs(ch[x][0]);
    dfs(ch[x][1]);
}
void insert(int &x,int pos,int fa){
    if(!x){x=pos,pre[pos]=fa;return ;}
    if(key[x]>key[pos])insert(ch[x][0],pos,x);
    else insert(ch[x][1],pos,x);
    up(x);
}
void merge(int x,int y){
    splay(x,0);splay(y,0);
    if(size[x]>size[y])swap(x,y);
    tot=0;dfs(x);int last=y;
    for(int i=1;i<=tot;i++)newnode(st[i],0,key[st[i]]),insert(last,st[i],0),splay(st[i],0),last=st[i];
}
int find1(int x,int sz){
    if(sz==size[ch[x][0]]+1)return x;
    if(sz<=size[ch[x][0]])return find1(ch[x][0],sz);
    else return find1(ch[x][1],sz-size[ch[x][0]]-1);
}
ll check(int x,int t){
    splay(x,0);int t1=find1(x,t);
 //   cout<<t<<"----===="<<" "<<t1<<endl;
    splay(t1,0);
    return sum[ch[t1][0]]+key[t1];
}
int slove(int x,ll k){
    splay(x,0);
    if(sum[x]<=k)return size[x];
    int r=size[x];int ans=0;int l=1;
    while(l<=r){
    int mid=(l+r)>>1;
//  cout<<check(x,mid)<<" "<<l<<" "<<r<<endl;
    if(check(x,mid)<=k)ans=mid,l=mid+1;
    else r=mid-1;
    }
    return ans;
}
ll minn,m;int n;
void dfs1(int v){
    //cout<<v<<"::::"<<endl;
    for(int i=0;i<vec[v].size();i++){
    if(vec[v][i]!=f[v]){
        //merge(v,vec[v][i]);
        dfs1(vec[v][i]);
        merge(v,vec[v][i]);
       // debug(v);
    }
    }
  //  cout<<slove(v,m)<<"======"<<a[v]<<" "<<v<<endl;
  //  debug(v);
    minn=max(minn,1ll*slove(v,m)*a[v]);
 //   cout<<minn<<endl;
    //debug(v);
}
int main(){
    n=read();m=read();
    int v,bi,ci;int rt;
    for(int i=1;i<=n;i++){
    v=read();ci=read();a[i]=read();
    f[i]=v;
    if(!v)rt=i;
    vec[v].push_back(i);
    vec[i].push_back(v);
    newnode(i,0,ci);
    }
  //  for(int i=1;i<=n;i++){
//  for(int j=0;j<vec[i].size();j++)cout<<vec[i][j]<<"::::";
//  cout<<endl;
 //   }
   // cout<<rt<<endl;
    minn=0;
    dfs1(rt);
    printf("%lld
",minn);
    return 0;
}

2809: [Apio2012]dispatching

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 5206 Solved: 2679
[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

HINT

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

用户的满意度为 2 ，是可以得到的用户满意度的最大值。