参考题目：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;
}
好文章！666，学习了
If some one wants expert view concerning blogging after that i recommend him/her to visit this
web site, Keep up the nice work.
Hiya very cool web site!! Man .. Beautiful .. Superb ..
I’ll bookmark your blog and take the feeds additionally?
I am happy to search out so many helpful info right here in the
put up, we want work out more techniques on this regard, thanks for sharing.
. . . . .
Pretty! This has been a really wonderful post.
Thanks for supplying these details.
whoah this blog is great i like reading your articles.
Keep up the good work! You know, many individuals are searching round for this
information, you could help them greatly.
Because the admin of this website is working, no uncertainty very shortly it will
be well-known, due to its feature contents.
Hi there it’s me, I am also visiting this website regularly, this site is truly
fastidious and the visitors are actually sharing good thoughts.
Today, I went to the beachfront with my children. I found
a sea shell and gave it to my 4 year old daughter and said
“You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.
There was a hermit crab inside and it pinched her ear. She never wants to go back!
LoL I know this is completely off topic but I had to tell someone!
Very nice post. I just stumbled upon your weblog and wanted to say that I have
really enjoyed surfing around your blog posts. After all I
will be subscribing to your rss feed and I hope you write again very soon!
I always emailed this webpage post page to
all my friends, because if like to read it then my
links will too.
I think this is one of the most vital info for me.
And i am glad reading your article. But wanna remark on few general things,
The website style is wonderful, the articles is really great : D.
Good job, cheers
Hello it’s me, I am also visiting this web page daily,
this website is really pleasant and the users are really sharing pleasant
thoughts.
I needed to thank you for this very good read!! I absolutely
enjoyed every bit of it. I have got you saved as a favorite to look at
new stuff you post…
Hi everybody, here every person is sharing such experience, so it’s nice to read this web site, and I used to pay a visit
this webpage daily.
WOW just what I was looking for. Came here by searching for coconut oil
I enjoy assembling utile info, this post has got me even more info! .
Thanks to my father who informed me concerning
this webpage, this website is really amazing.
Usually I don’t learn article on blogs, however I
would like to say that this write-up very pressured me to check out and do
so! Your writing taste has been surprised me. Thanks, very nice post.
I always spent my half an hour to read this web site’s content everyday along with a cup of coffee.
Attractive portion of content. I just stumbled upon your web site and in accession capital to assert that I get in fact loved account your blog posts.
Anyway I’ll be subscribing to your augment or even I fulfillment you get entry to consistently rapidly.
Hello there, I found your site via Google whilst looking for a comparable
matter, your site got here up, it appears great. I have bookmarked it in my google bookmarks.
Hello there, just turned into aware of your blog via Google, and found that
it is truly informative. I’m going to be careful for brussels.
I’ll appreciate if you happen to continue this in future.
A lot of folks can be benefited out of your writing.
Cheers!
Oh my goodness! Amazing article dude! Thank you,
However I am encountering troubles with your RSS. I don’t
know the reason why I can’t join it. Is there anyone else getting the same RSS issues?
Anybody who knows the solution can you kindly respond?
Thanks!!
Your style is so unique in comparison to other
folks I have read stuff from. Many thanks for posting when you have the opportunity, Guess I’ll just book mark this site.
Wonderful blog! I found it while browsing on Yahoo News.
Do you have any tips on how to get listed in Yahoo
News? I’ve been trying for a while but I never
seem to get there! Appreciate it
Hey there exceptional website! Does running a blog similar to this require a great deal of work?
I’ve absolutely no knowledge of programming but I was hoping to start my own blog in the near future.
Anyhow, if you have any ideas or techniques for new blog owners please share.
I know this is off subject but I just had to ask. Appreciate it!
If you are going for most excellent contents like me, simply pay a
visit this web site every day as it offers quality contents, thanks
Its like you read my thoughts! You seem to understand a lot about this,
like you wrote the book in it or something.
I feel that you could do with a few percent to force the message house a bit, however
instead of that, this is excellent blog. A great read.
I’ll definitely be back.
Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your
website? My blog is in the very same niche as yours
and my visitors would definitely benefit from a lot of the
information you provide here. Please let me know if this okay with
you. Cheers!
What i don’t understood is if truth be told how you’re not really a lot
more smartly-liked than you may be now. You’re so intelligent.
You know therefore significantly in terms of this matter, made me personally consider it from numerous
varied angles. Its like women and men don’t seem to be interested
except it’s one thing to do with Girl gaga!
Your personal stuffs great. All the time take care of it up!
My brother suggested I might like this blog.
He was totally right. This post actually made my day.
You cann’t imagine just how much time I had spent for this info!
Thanks!
Howdy this is kinda of off topic but I was wanting to know if blogs use WYSIWYG editors or if you have to manually code with HTML. I’m starting a blog soon but have no coding knowledge so I wanted to get guidance from someone with experience. Any help would be greatly appreciated!