题意:链接 方法:可并堆 解析: 水题，但注意过程爆int. 方法就是找到树的根节点，之后扫，将每个子树什么的看做一个堆，然后之间合并，如果堆中的sum和超过了m，，则去掉最大的，继续添加，这个显然啊。 然后每次处理完一个点，用堆中解更新答案。 比前两道水 代码: #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 100100 using namespace std; typedef long long ll; int n,m,all_root,cnt; ll ans; int head[N],h[N],fa[N],ch[N][2],root[N]; ll sum[N],val[N],lead[N],size[N]; struct node { int from,to,next; }edge[N]; int find(int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);} void pushup(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];size[x]=size[ch[x][0]]+size[ch[x][1]]+1;} void init() { memset(head,-1,sizeof(head)),cnt=1; for(int i=1;i<=n;i++)fa[i]=i; } void edgeadd(int from,int to) { edge[cnt].to=to,edge[cnt].next=head[from],head[from]=cnt++; } int merge(int x,int y) { if(!x)return y; if(!y)return x; if(val[x]<val[y])swap(x,y); ch[x][1]=merge(ch[x][1],y); if(h[ch[x][1]]>h[ch[x][0]])swap(ch[x][1],ch[x][0]); h[x]=h[ch[x][1]]+1; return x; } void dfs(int x) { sum[x]=val[x],size[x]=1; for(int i=head[x];i!=-1;i=edge[i].next) { int to=edge[i].to; dfs(to); sum[x]+=sum[to];size[x]+=size[to]; fa[x]=merge(fa[x],fa[to]); } while(sum[x]>m) { sum[x]-=val[fa[x]],size[x]--; fa[x]=merge(ch[fa[x]][0],ch[fa[x]][1]); } ans=max(lead[x]*size[x],ans); } int main() { h[0]=-1; scanf("%d%d",&n,&m); init(); for(int i=1;i<=n;i++) { int f,v,l; scanf("%d%d%d",&f,&v,&l); if(!f){all_root=i,val[i]=v,lead[i]=l,size[i]=1;continue;} edgeadd(f,i); val[i]=v,lead[i]=l,size[i]=1; } dfs(all_root); printf("%lld\n",ans); }