最近又重新学了一遍左偏树，然后做了这道题……
题目描述很麻烦……（尤其是我根本不知道那个master到底能干嘛），其实就是要求选取一个节点，在其子树内找到花费不超过M的最多的人数*这个节点自身价值。然后选取某一个点使得价值最大。
因为这个题和普通的情况不大一样，别的都是要求什么自身价值高，这个不用，只要人多就行，那咱们贪心一下，肯定是从花费小的人开始选，也就是我们维护一个大根堆，如果这个堆中所有值的和超过了限制的话，就直接把花费最大的踢掉，因为他后来无论如何也不可能被选取了。
所以我们可以考虑树DP，首先向下递归搜索，然后在返回的时候，既然对于每个节点我们建立了大根堆，在返回的时候肯定是要合并的，这个过程我们就可以直接用左偏树维护，每次在合并结束的时候更新答案即可。注意本题要开longlong
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') #define lowbit(x) x & (-x) using namespace std; typedef long long ll; const int M = 200005; const int INF = 1000000009; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct node { int next,to; }e[M]; int head[M],ecnt,size[M],lc[M],rc[M],dis[M],root[M],n,m; ll sum[M],p[M],c[M],x,cost[M],ans; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void pushup(int x) { sum[x] = sum[lc[x]] + sum[rc[x]] + cost[x]; size[x] = size[lc[x]] + size[rc[x]] + 1; } int merge(int x,int y) { if(!x || !y) return x | y; if(cost[x] < cost[y]) swap(x,y); rc[x] = merge(rc[x],y); if(dis[lc[x]] < dis[rc[x]]) swap(lc[x],rc[x]); dis[x] = dis[rc[x]] + 1; pushup(x); return x; } int split(int x) { return merge(lc[x],rc[x]); } void dfs(int x,int fa) { cost[x] = sum[x] = c[x]; rc[x] = lc[x] = 0,size[x] = 1,root[x] = x; for(int i = head[x];i;i = e[i].next) { if(e[i].to == fa) continue; dfs(e[i].to,x); root[x] = merge(root[x],root[e[i].to]);//合并操作 } while(sum[root[x]] > m && size[root[x]]) root[x] = split(root[x]);//删除操作 ans = max(ans,(ll)size[root[x]] * (ll)p[x]); } int main() { n = read(),m = read(); rep(i,1,n) x = read(),c[i] = read(),p[i] = read(),add(x,i),add(i,x); dfs(1,0); printf("%lld ",ans); return 0; }