【BZOJ2809】【APIO2012】派遣

给一棵树，每个点有一个薪水和一个领导力

选定一个点\(x\)和它子树内的\(k\)个点，并且这\(k\)个点的薪水之和不超过预算，使\(x\)的领导力与\(k\)的乘积最大。

天辣原来这就是传说中的可并堆原题我居然看不出

每个点维护一个大根可并堆使得堆内元素和不超过预算，不断向上合并即可。。

平板电视大法好！

// <2809.cpp> - 06/28/16 20:16:13
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=100001;
const int INF=1e9;
int f[MAXN],v[MAXN],l[MAXN];
lol sum[MAXN];
__gnu_pbds::priority_queue <int> q[MAXN];
int main(){
    int n=gi(),m=gi();
    for(int i=1;i<=n;i++)f[i]=gi(),v[i]=gi(),l[i]=gi();
    lol ans=0;
    for(int i=n;i;i--){
        q[i].push(v[i]);sum[i]+=v[i];
        while(sum[i]>m){
            sum[i]-=q[i].top();
            q[i].pop();
        }
        ans=max(ans,1ll*q[i].size()*l[i]);
        sum[f[i]]+=sum[i];
        q[f[i]].join(q[i]);
    }
    printf("%lld",ans);
    return 0;
}

// <2809.cpp> - 06/28/16 20:16:13

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <ext/pb_ds/priority_queue.hpp>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

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

if(ch=='-')fh=-1,ch=getchar();

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

return fh*res;

}

const int MAXN=100001;

const int INF=1e9;

int f[MAXN],v[MAXN],l[MAXN];

lol sum[MAXN];

__gnu_pbds::priority_queue <int> q[MAXN];

int main(){

int n=gi(),m=gi();

for(int i=1;i<=n;i++)f[i]=gi(),v[i]=gi(),l[i]=gi();

lol ans=0;

for(int i=n;i;i--){

q[i].push(v[i]);sum[i]+=v[i];

while(sum[i]>m){

sum[i]-=q[i].top();

q[i].pop();

}

ans=max(ans,1ll*q[i].size()*l[i]);

sum[f[i]]+=sum[i];

q[f[i]].join(q[i]);

}

printf("%lld",ans);

return 0;

}