BZOJ2809

发表于 | 分类于 |

题目传送门

Description

有$N$个忍者及一个Master，忍者从$1$~$N$编号，Master编号为0，忍者之间有从属关系，上级的编号一定比下属小。

每个忍者有一个工资和领导能力值。

现要求派出一些忍者并确定一名领导者，派出忍者要支付工资。领导者也可以被派出，但派出就付工资，不派出就不用，领导者必须是派出的所有忍者的上级（祖先）。

求：在预算范围内派出的忍者数*领导者的领导能力值的最大值。

Input

第一行：$N$和$M$，$N$表示忍者数，$M$表示工资总预算。

接下来$N$行：每行三个整数，$B_i$、$C_i$、$L_i$，其中$B_i$表示上级，$C_i$表示工资，$L_i$表示领导能力值。

Output

一行，一个数：答案。

Solution

用主席树做。

建起来明显就是一棵树。

按DFS遍历一遍（前序遍历）并记录每个点进去和出来的时间，分别用数组$in$和数组$out$记录。

以工资大小顺序为下标，累加总工资和人数。

再以$in$数组的时间先后为顺序，把点一个一个加进去，更新原本那颗树。

不难发现，每个点的子孙的$in$时间就在他进去和出去的时间的范围内。

所以枚举每个点，用它$out$时间时的线段树减去$in$时间时的线段树，就剩仅由它子孙信息构成的线段树了。

在此基础上查找合法的工资数的最大值，以此找出改点所能派出的最大人数。然后在乘上改点的领导能力，取最大值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=100100;
int n,m;
long long ans;
struct Ninja
{
    int fa,cost,l;
}ninja[maxn];
struct EDGE
{
    int ap;
    EDGE *next;
}edge[maxn],*ind[maxn];
int el;
void input(int x,int y)
{
    edge[++el].ap=y;
    edge[el].next=ind[x];
    ind[x]=&edge[el];
}
 
struct idnk
{
    int num,adr;
}b[maxn];
int c[maxn];
bool cmp(idnk x,idnk y){return x.num<y.num;}
void dis()
{
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;i++) c[b[i].adr]=i;
}
 
 
int T,din[maxn],dout[maxn],d[maxn];
void dfs(int x)
{
    din[x]=++T;
    d[T]=x;
    for(EDGE *k=ind[x];k!=NULL;k=k->next)
        dfs(k->ap);
    dout[x]=T;
}
 
struct TREE
{
    long long sumc;
    long long sumn;
    TREE *l,*r;
}tree[maxn*20],*root[maxn];
int tl;
TREE *build(int l,int r)
{
    int N=++tl;
    if(l==r) return &tree[N];
     
    int mid=(l+r)/2;
    tree[N].l=build(l,mid);
    tree[N].r=build(mid+1,r);
    return &tree[N]; 
}
 
TREE *update(int l,int r,int find,int add,TREE *k)
{
    int N=++tl;
    if(l==r)
    {
        tree[N].sumc=k->sumc+add;
        tree[N].sumn=1;
        return &tree[N];
    }
    int mid=(l+r)/2;
    if(find<=mid) tree[N].l=update(l,mid,find,add,k->l),tree[N].r=k->r;
    else tree[N].l=k->l,tree[N].r=update(mid+1,r,find,add,k->r);
    tree[N].sumc=tree[N].l->sumc+tree[N].r->sumc;
    tree[N].sumn=tree[N].l->sumn+tree[N].r->sumn;
    return &tree[N];
}
 
long long work(int l,int r,long long maxm,TREE *tl,TREE *tr)
{
    if(l==r) return tr->sumc-tl->sumc<=maxm ? 1 : 0;
    int mid=(l+r)/2;
    if(tr->sumc-tl->sumc<=maxm) return tr->sumn-tl->sumn;
    else if(tr->l->sumc-tl->l->sumc>maxm) return work(l,mid,maxm,tl->l,tr->l);
    else return tr->l->sumn-tl->l->sumn+work(mid+1,r,maxm-tr->l->sumc+tl->l->sumc,tl->r,tr->r);
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&ninja[i].fa,&ninja[i].cost,&ninja[i].l);
        b[i].adr=i;
        b[i].num=ninja[i].cost;
        input(ninja[i].fa,i);
    }
    dis();
    for(EDGE *k=ind[0];k!=NULL;k=k->next)
        dfs(k->ap);
    root[0]=build(1,n);
    for(int i=1;i<=n;i++) root[i]=update(1,n,c[d[i]],ninja[d[i]].cost,root[i-1]);
     
    for(int i=1;i<=n;i++)
    {
        long long sumn=work(1,n,m,root[din[i]-1],root[dout[i]]);
        ans=max(ans,sumn*ninja[i].l);
    }
    printf("%lld",ans);
    return 0;
}