标签：swap   恢复   忍者   统计   for   gis   预算   大根堆   范围   

「Luogu1552」[APIO2012]派遣

最近状态都不是很好，写完这个题感觉手感好像恢复了一些

problem

Solution

这个数据范围显然树形DP是做不了的

我们考虑，在预算范围内，选中的忍者越多越好，那么我们在一棵子树中选中的忍者一定是薪水最少的若干个

对每个节点维护一个大根堆，并记录每个堆的大小和堆中元素的权值和

考虑一棵子树时，用类似树形DP的方法将所有儿子合并到根

如果堆中元素权值和大于预算，不断弹出堆顶直到权值和不大于预算即可

最后对子树进行统计，更新答案

可并堆可以用左偏树实现

另外，还需要记录每个节点对应的左偏树的根的编号

Code

一开始没开long long还wa了一发

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;

template void read(T &t)
{
    t=0;int f=0;char c=getchar();
    while(!isdigit(c)){f|=c=='-';c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int maxn=100000+5;
int n,root;
ll m;
ll mng[maxn];
ll ans;

struct edge
{
    int u,v,nxt;
}g[maxn];

int head[maxn],ecnt;
void eADD(int u,int v)
{
    g[++ecnt].u=u;
    g[ecnt].v=v;
    g[ecnt].nxt=head[u];
    head[u]=ecnt;
}

int rec[maxn];
struct node
{
    int ls,rs,dist;
    ll val,siz,sum;
}mxh[maxn];

int Merge(int x,int y)
{
    if(!x || !y)return x+y;
    if(mxh[x].valm && mxh[rec[u]].siz)
        rec[u]=Pop(rec[u]);
    ans=max(ans,1ll*mxh[rec[u]].siz*mng[u]);
}

int main()
{
    read(n),read(m);
    for(register int i=1;i

「Luogu1552」[APIO2012]派遣

标签：swap   恢复   忍者   统计   for   gis   预算   大根堆   范围   

原文地址：https://www.cnblogs.com/lizbaka/p/10657928.html