链接
https://www.luogu.org/problemnew/show/P1552
思路
忍者数量肯定越多越好
那就从下到上的合并它的孩子
左偏树的话
顺便维护一个tot，大头堆，如果tot大于了m，把大的删掉
如果左偏树忘干净了或者没学的话
线段树合并也是个不错的选择
直接权值线段树合并就好，内存30倍会炸，也许是我没离散化的缘故吧
查询在线段树上面二分
左偏树代码
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ll long long
using namespace std;
const int maxn=100047;
inline int read() {
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
struct edge {
int v,nxt;
}e[maxn];
int head[maxn],tot;
void add_edge(int u,int v) {
e[++tot].v=v;e[tot].nxt=head[u];head[u]=tot;
}
int n,m,mone;
ll sum[maxn],ans;
int size[maxn];
int ch[maxn][2],dis[maxn],val[maxn],xs[maxn];
int work(int a,int b) {
if(!a||!b) return a+b;
if(val[a]<val[b]) swap(a,b);
ch[a][1]=work(ch[a][1],b);
if(dis[ch[a][0]]<dis[ch[a][1]]) swap(ch[a][0],ch[a][1]);
dis[a]=dis[ch[a][1]]+1;
return a;
}
int merge(int x,int y) {
int tmp=work(x,y);
y=x^y^tmp,x=tmp;
sum[x]+=sum[y];
size[x]+=size[y];
return tmp;
}
int delet(int x) {
int tmp=work(ch[x][0],ch[x][1]);
size[tmp]=size[x]-1;
sum[tmp]=sum[x]-val[x];
return tmp;
}
int dfs(int u) {
int rt=u;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
int tmp=dfs(v);
rt=merge(rt,tmp);
}
while(sum[rt]>mone) rt=delet(rt);
ans=max(ans,xs[u]*(ll)size[rt]);
return rt;
}
int main() {
n=read(),mone=read();
int root;
FOR(i,1,n) {
int x=read();
val[i]=read();xs[i]=read();
sum[i]=val[i];size[i]=1;
if(x) add_edge(x,i);
else root=i;
}
int wuyong=dfs(root);
cout<<ans<<"
";
return 0;
}
线段树合并代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
using namespace std;
const int N=1e5+7;
int read() {
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
int n,m,money[N],leader[N],rt[N];
vector<int> G[N];
struct node {
int l,r,siz;
ll tot;
}e[N*30];
void pushup(int rt) {
e[rt].siz=e[e[rt].l].siz+e[e[rt].r].siz;
e[rt].tot=e[e[rt].l].tot+e[e[rt].r].tot;
}
int cnt;
void insert(int l,int r,int L,int &rt) {
rt=++cnt;
if(l==r) {
e[rt].siz++;
e[rt].tot+=l;
return;
}
int mid=(l+r)>>1;
if(L<=mid) insert(l,mid,L,e[rt].l);
else insert(mid+1,r,L,e[rt].r);
pushup(rt);
}
int merge(int l,int r,int x,int y) {
if(!x||!y) return x+y;
if(l==r) {
e[x].siz+=e[y].siz;
e[x].tot+=e[y].tot;
return x;
}
int mid=(l+r)>>1;
e[x].l=merge(l,mid,e[x].l,e[y].l);
e[x].r=merge(mid+1,r,e[x].r,e[y].r);
pushup(x);
return x;
}
int query(int l,int r,int k,int rt) {
if(l==r) return k>=e[rt].tot ? e[rt].siz : 0;
int mid=(l+r)>>1;
if(e[e[rt].l].tot>=k) return query(l,mid,k,e[rt].l);
else return e[e[rt].l].siz+query(mid+1,r,k-e[e[rt].l].tot,e[rt].r);
}
ll ans;
void dfs(int u) {
insert(1,1000000000,money[u],rt[u]);
for(vector<int>::iterator it=G[u].begin();it!=G[u].end();++it) {
dfs(*it);
rt[u]=merge(1,1000000000,rt[u],rt[*it]);
}
ans=max(ans,(ll)leader[u]*query(1,1000000000,m,rt[u]));
}
int main() {
n=read(),m=read();
for(int i=1;i<=n;++i) {
int x=read();
money[i]=read();
leader[i]=read();
G[x].push_back(i);
}
dfs(1);
printf("%lld",ans);
return 0;
}