题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2809
我是来练习斜堆的 = ̄ω ̄=
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
const int N = 100000+9;
LL vout;
int led[N],n,m,arr[N],rt;
vector<int> G[N];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}
namespace Skew_Heap{
#define SHP Skew_Heap
int ch[N][2],sz[N],val[N],root[N],cnt;
LL sum[N];
inline void maintain(int w) {
sz[w] = sz[ch[w][0]] + sz[ch[w][1]] + 1;
sum[w] = sum[ch[w][0]] + sum[ch[w][1]] + val[w];
}
int Merge(int a, int b){
if (!a || !b) return a+b;
else {
if (val[b] > val[a]) swap(a,b);
ch[a][1] = Merge(ch[a][1],b);
swap(ch[a][0],ch[a][1]); maintain(a);
return a;
}
}
inline void pop(int w){
root[w] = Merge(ch[root[w]][0],ch[root[w]][1]);
}
inline void insert(int w, int v){
val[++cnt] = sum[cnt] = v; sz[cnt] = 1;
root[w] = Merge(root[w],cnt);
}
};
int main(){
using namespace Skew_Heap;
n = read(); m = read();
for (int i=1,tmp;i<=n;i++) {
G[read()].push_back(i);
arr[i] = read(); led[i] = read();
}
for (int i=n;i;i--) {
for (int j=0,lim=G[i].size();j<lim;j++) root[i] = Merge(root[i],root[G[i][j]]);
insert(i,arr[i]); while (root[i] && sum[root[i]] > m) pop(i);
vout = max(vout,(LL)sz[root[i]]*led[i]);
}
printf("%lld\n",vout);
return 0;
}