题目传送门：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;
}
Hi there, this weekend is good designed for me, as this time i am reading
this fantastic informative piece of writing here at my residence.
Keep this going please, great job!
I constantly spent my half an hour to read this
weblog’s articles all the time along with a mug of coffee.
With havin so much content and articles do you ever run into any problems of plagorism or copyright
violation? My website has a lot of completely unique content I’ve either authored myself or outsourced
but it looks like a lot of it is popping it up all over the internet
without my authorization. Do you know any ways to help stop content from being ripped
off? I’d really appreciate it.
Your style is really unique in comparison to other people I’ve
read stuff from. Thank you for posting when you have the opportunity,
Guess I will just book mark this site.
Hey just wanted to give you a quick heads up.
The words in your article seem to be running off the screen in Internet explorer.
I’m not sure if this is a formatting issue or something to do with web browser
compatibility but I figured I’d post to let you know.
The layout look great though! Hope you get the issue fixed soon.
Many thanks
I couldn’t refrain from commenting. Well written!
Hey there! Do you use Twitter? I’d like to follow you if that would be okay.
I’m undoubtedly enjoying your blog and look forward to
new updates.
whoah this weblog is wonderful i love studying your posts.
Stay up the good work! You understand, lots of people are searching around for this information, you
can aid them greatly.
Hi there, I discovered your blog by way of Google even as looking for a related
matter, your site got here up, it looks great.
I have bookmarked it in my google bookmarks.
Hi there, just became alert to your blog through Google, and found that it’s
truly informative. I’m going to watch out for brussels. I will appreciate for those who proceed this in future.
Numerous other people can be benefited from your writing.
Cheers!
I’m extremely impressed with your writing abilities and also
with the format in your weblog. Is this a paid topic or did you customize it yourself?
Anyway stay up the nice high quality writing, it’s uncommon to peer a nice blog like this one these days..
Hello there, just became alert to your blog through Google, and found
that it is truly informative. I’m going to watch out for brussels.
I’ll be grateful if you continue this in future. Numerous
people will be benefited from your writing. Cheers!
We are a group of volunteers and opening a new scheme in our community.
Your website offered us with valuable info to work on. You
have done a formidable job and our whole community will be grateful to you.
Wonderful web site. A lot of useful information here. I’m sending it to several friends ans also sharing in delicious. And certainly, thanks for your effort!
bookmarked!!, I really like your web site!
An outstanding share! I have just forwarded this onto a co-worker who was doing
a little research on this. And he actually
bought me dinner simply because I found it for him…
lol. So allow me to reword this…. Thank YOU for
the meal!! But yeah, thanks for spending the time to talk about
this issue here on your internet site.
Very nice post. I just stumbled upon your weblog and wanted to say
that I’ve truly enjoyed browsing your blog posts. In any case
I’ll be subscribing to your rss feed and I hope you write again very soon!
Touche. Outstanding arguments. Keep up the amazing work.
Every weekend i used to pay a quick visit this site,
for the reason that i wish for enjoyment, as this this site conations
genuinely pleasant funny material too.
Thanks for finally writing about >【BZOJ 2809】[Apio2012] dispatching –
Qizy’s Database <Loved it!
Hi there Dear, are you actually visiting this web site daily,
if so then you will without doubt obtain nice
knowledge.
I know this if off topic but I’m looking into starting my own blog and was curious what all is
needed to get set up? I’m assuming having a blog like yours would cost a pretty penny?
I’m not very internet savvy so I’m not 100% certain. Any suggestions or advice would be greatly appreciated.
Kudos
Thanks for your marvelous posting! I seriously enjoyed reading it,
you’re a great author.I will be sure to bookmark your blog and may come back later in life.
I want to encourage yourself to continue your great work, have a nice day!
I’ve been exploring for a bit for any high quality articles or weblog posts on this kind of space .
Exploring in Yahoo I finally stumbled upon this web site.
Studying this information So i am glad to exhibit
that I have a very excellent uncanny feeling I found out just what I needed.
I such a lot undoubtedly will make certain to don?t omit this web site and provides it a look regularly.
Good post however I was wondering if you could write a litte
more on this subject? I’d be very grateful if you could elaborate a little
bit further. Thank you!
Whats up this is somewhat 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 skills so I
wanted to get advice from someone with experience. Any help would be
greatly appreciated!
Generally I don’t learn post on blogs, however I wish to say that this write-up very compelled me to check out and
do so! Your writing style has been surprised me. Thanks, very
nice post.
I really wanted to make a brief message to be able to express gratitude to you for the magnificent tips and tricks you are showing here. My incredibly long internet research has finally been rewarded with awesome information to write about with my companions. I would repeat that we website visitors actually are undeniably fortunate to live in a decent network with many lovely people with valuable tactics. I feel truly fortunate to have encountered the web pages and look forward to tons of more amazing times reading here. Thanks a lot once more for all the details.