题面
我捡到了一棵树。这棵树上有 n 个点，被标号为 1…n，其中 1号结点为根节点。
奇怪的是，每个点有一个体积 c[i]。
更奇怪的是，每个点有一个权值 a[i]。
更更奇怪的是，每个点上有一个容积为 v[i]的箱子。
这棵树说，每个点上的箱子可以装入若干个该点子树内的点（包括自身），但是要满足被装入的点的体积之和不超过箱子的容积。而一个箱子的价值为其装入点的个数与箱子对应点的权值的乘积。
我想要知道，对于每一个箱子的所有装入点的方案，哪个方案中箱子的价值最高。为了简便，你只需要告诉我这个价值就行了。
对于100%的数据，1≤n≤2e5,0≤c[i],a[i]≤1e9,0≤v[i]≤2e14。
思路
一道不错的线段树合并入门题。比阴间的尾巴不知道好到哪里去了。
做决策确实是很简单的贪心，从自己子树里的点从小往大拿就完事。问题在于怎么维护这个顺序，总不可能每次都排一次序。
答案是使用线段树合并。
对每个节点开一个动态开点权值线段树，维护当前节点子树中的所有节点的数量与代价和。做树形 DP 的过程中处理完了儿子直接往上合并即可。
查询时直接在自己的线段树上二分即可。
说起来这篇题解是还在赛时写的，不晓得会不会有大聪明爆搜题面然后找到这篇题解。
啊，算了，不管了，伞兵51Nod比赛被创烂活该。
代码
const ll maxn=2e5+5;
struct node{
ll ls,rs,val,cnt;
}t[maxn<<5];
ll tot;
#define mid ((l+r)>>1)
void upd(ll x){
t[x].val=t[t[x].ls].val+t[t[x].rs].val;
t[x].cnt=t[t[x].ls].cnt+t[t[x].rs].cnt;
}
void insert(ll x,ll l,ll r,ll k){
t[x].cnt++;
t[x].val+=k;
if(l==r)return ;
if(k<=mid){
if(!t[x].ls)t[x].ls=++tot;
insert(t[x].ls,l,mid,k);
}
if(k>mid){
if(!t[x].rs)t[x].rs=++tot;
insert(t[x].rs,mid+1,r,k);
}
}
ll query(ll x,ll l,ll r,ll k){
// wk(l),wk(r),we(k);
if(l==r){
return min(t[x].cnt,k/l);
}
ll res=0;
if(k<t[t[x].ls].val){
return query(t[x].ls,l,mid,k);
}
res+=t[t[x].ls].cnt;
if(!t[x].rs)return res;
res+=query(t[x].rs,mid+1,r,k-t[t[x].ls].val);
return res;
}
void merge(ll x,ll y,ll l,ll r){
if(l==r){
t[x].val+=t[y].val;
t[x].cnt+=t[y].cnt;
return ;
}
if(t[x].ls){
if(t[y].ls){
merge(t[x].ls,t[y].ls,l,mid);
}
}
if(!t[x].ls){
if(t[y].ls)t[x].ls=t[y].ls;
}
if(t[x].rs){
if(t[y].rs){
merge(t[x].rs,t[y].rs,mid+1,r);
}
}
if(!t[x].rs){
if(t[y].rs)t[x].rs=t[y].rs;
}
upd(x);
}
const ll maxv=1e9;
vector<ll>e[maxn];
ll c[maxn],w[maxn],a[maxn];
ll n,ans;
void dfs(ll x,ll fa){
for(auto v:e[x]){
if(v==fa)continue;
dfs(v,x);
merge(x,v,0,maxv);
}
ll res=query(x,0,maxv,w[x]);
// wk(x),wk(t[x].cnt),we(res);
ans=max(a[x]*res,ans);
}
void solve(){
n=R;
tot=n;
for(ll i=1;i<n;i++){
ll x=R,y=R;
e[x].push_back(y);
e[y].push_back(x);
}
for(ll i=1;i<=n;i++){
c[i]=R,w[i]=R,a[i]=R;
insert(i,0,maxv,c[i]);
}
dfs(1,0);
we(ans);
return ;
}