注释中的代码全部加上了root[]
by DOTime @ 2017-09-13 08:44:37
你写得丑
by Crazy01 @ 2017-09-13 09:33:47
玄学理解吧。。我也晕。。
by Crazy01 @ 2017-09-13 09:35:34
你每一步更新ans求出的是以当前处理的节点为管理者的最有答案，也就是说，管理者必须选，如果你处理root[x]的话可能会导致管理者被弹出(?)我也不确定，我的个人感觉是这样的
by Crazy01 @ 2017-09-13 09:39:12
最优
by Crazy01 @ 2017-09-13 09:39:32
不对
我好像搞错了。。。
by Crazy01 @ 2017-09-13 09:40:48
@[时钟之门](/space/show?uid=38711) 实际上所有的点都是属于管理员now的，我没看完你的代码，但是在你弹出合并时你将根的sz--，你的根一直在变，之前的减一不就没了吗
by 星星之火 @ 2018-02-24 09:21:14
```cpp
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n,m,dad[N],a[N],b[N],rs[N],ls[N],dist[N],root[N];
int size[N],i,rt;
long long sum[N],ans;
vector<int>vec[N];
int merge(int x,int y){//堆合并操作(因为需要堆合并，所以使用左偏树)
if(!x||!y) return x|y;
if(a[x]<a[y]) swap(x,y);
rs[x]=merge(rs[x],y);
if(dist[rs[x]]>dist[ls[x]])swap(ls[x],rs[x]);
dist[x]=dist[rs[x]]+1;
return x;
}
void dfs(int x){
root[x]=x;//假设派遣管理员
sum[x]=a[x];
size[x]=1;//建一个只有一个节点的可并堆
for(int i=0;i<vec[x].size();i++){
dfs(vec[x][i]);//搜索儿子
sum[x]+=sum[vec[x][i]];//把当前节点的可并堆和儿子的合并
size[x]+=size[vec[x][i]];
root[x]=merge(root[x],root[vec[x][i]]);
}
while(sum[x]>m){//保证可并堆满足性质 (因为无论如何都需要保证<=m，因此现在删也没关系)
size[x]--;
sum[x]-=a[root[x]];
root[x]=merge(ls[root[x]],rs[root[x]]);
}
ans=max(ans,1ll*size[x]*b[x]);//管理员在一开始就已经确定，不被排遣也没关系，因为每个忍者都能传递消息
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d%d%d",&dad[i],&a[i],&b[i]);
if(!dad[i]) rt=i;//确定根
else vec[dad[i]].push_back(i);//建边
}
dfs(rt);//dfs
printf("%lld\n",ans);
return 0;
}
```@[时钟之门](/space/show?uid=38711)
你可以看看，我写了注释
by 星星之火 @ 2018-02-24 09:27:12