参考题目: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; }