BZOJ2809&&LG1552 APIO2012派遣(线段树合并)
题面
自己找去
HINT
简化一题面就是让你从每个点的子树中以(<=m)的代价选取尽可能多的点，然后乘上子树根的一个属性值，每个点做一遍取个(max)。看大家都是什么可并堆、dfs序+主席树，我的做法是对于每个节点开一颗权值线段树，每个节点维护(size)和(tot)，然后修改和线段树合并都是常规写法。
着重讲一下查询
这样的写法之后就是要实现查询用m的代价可以最多选择多少个点
inline int query(int p,long long rk,int l,int r){
if(!p) return 0;//如果进入了空节点，就肯定没有可选的，返回0
if(l==r){
int x=st[p].tot/st[p].size;return min((long long)rk/x,(long long)st[p].size);
//这里是重点，查询到该点的时候我还有rk的剩余，已经到叶子节点了，这个时候我们就要计算一下自己最多可以选多少个，如果能都选就都选，如果不能多选就尽量选满
}
long long now=st[ls(p)].tot;int mid=(l+r)>>1;
if(rk<=now) return query(ls(p),rk,l,mid);
else return st[ls(p)].size+query(rs(p),rk-now,mid+1,r);
}
其他的看代码吧
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ls(x) st[x].ch[0]
#define rs(x) st[x].ch[1]
using namespace std;
inline int read(){
int w=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+ch-48;
ch=getchar();
}
return w*f;
}
int n,m,cur,root[100010],a[100010],b[100010],val[100010],now[100010];
long long l[100010],ans[100010];
bool debug;
struct CHAIRMANTREE{
struct Node{
int size,ch[2];long long tot;
}st[6000010];
int tot;
inline void pushup(int x){
st[x].size=st[ls(x)].size+st[rs(x)].size;
st[x].tot=st[ls(x)].tot+st[rs(x)].tot;return;
}
inline int change(int p,int l,int r,int pos,int val){
if(!p)p=++tot;
if(l==r){
st[p].size+=1;st[p].tot+=val;return p;
}
int mid=(l+r)>>1;
if(pos<=mid) ls(p)=change(ls(p),l,mid,pos,val);
else rs(p)=change(rs(p),mid+1,r,pos,val);
pushup(p);return p;
}
inline int merge(int x,int y,int l,int r){
if(!x||!y) return x|y;
int p=++tot;
if(l==r){
st[p].size=st[x].size+st[y].size;
st[p].tot=st[x].tot+st[y].tot;return p;
}
int mid=(l+r)>>1;
ls(p)=merge(ls(x),ls(y),l,mid);
rs(p)=merge(rs(x),rs(y),mid+1,r);
pushup(p);return p;
}
inline int query(int p,long long rk,int l,int r){
if(!p) return 0;
if(l==r){
int x=st[p].tot/st[p].size;return min((long long)rk/x,(long long)st[p].size);
}
long long now=st[ls(p)].tot;int mid=(l+r)>>1;
if(rk<=now) return query(ls(p),rk,l,mid);
else return st[ls(p)].size+query(rs(p),rk-now,mid+1,r);
}
}TREE;
int cnt,head[100010];
struct Edge{
int from,to,next;
}edge[200010];
inline void addedge(int u,int v){
cnt++;
edge[cnt].from=u;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
map<int,int> mapp;
inline void prework(){
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(!mapp[a[i]]){
cur++;mapp[a[i]]=cur;b[cur]=a[i];
}
}
for(int i=1;i<=n;i++){
val[i]=mapp[val[i]];
}
}
inline void dfs(int u){
root[u]=TREE.change(root[u],1,cur,val[u],now[u]);
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;dfs(v);
root[u]=TREE.merge(root[u],root[v],1,cur);
}
if(debug)cout<<"test"<<u<<endl;
ans[u]=(long long)TREE.query(root[u],m,1,cur);
if(debug){
cout<<u<<" "<<ans[u]<<endl;
}
}
signed main(){
n=read();m=read();
for(int i=1;i<=n;i++){
int x=read();addedge(x,i);
now[i]=a[i]=val[i]=read();l[i]=read();
}
prework();
//debug=true;
dfs(1);
long long Ans=-1;
for(int i=1;i<=n;i++){
//cout<<l[i]<<" "<<ans[i]<<endl;
Ans=max(Ans,l[i]*ans[i]);
}
cout<<Ans<<endl;
return 0;
}