链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1040
数据生成器：http://paste.ubuntu.com/23618220/
神犇题解：http://blog.csdn.net/popoqqq/article/details/39748135
题解
看到这个题，感觉除了网络流之外别无他法
结果这货是个基环森林啊！
I well vegetable are!
这个问题搬到树上去大家都会做
原题好像叫“没有上司的舞会”？
考虑给树加上一条边之后会发生什么变化：
这条非树边要么两段的点选一个，要么都不选
于是特殊处理一下，跑三遍树上DP就可以辣！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1000000+9;
const int M = N << 1;
int head[N],to[M],nxt[M];
int n,val[N],aim[N],tag[N],lb,rb;
LL vout,f[N][2];
inline void Add_Edge(const int u, const int v) {
static int T = 1;
to[++T] = v; nxt[T] = head[u]; head[u] = T;
to[++T] = u; nxt[T] = head[v]; head[v] = T;
}
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;
}
void DFS(int w, int f) {
tag[w] = 1;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f && to[i]) {
if (tag[to[i]]) {
lb = w; rb = to[i];
to[i] = to[i^1] = 0;
} else {
DFS(to[i], w);
}
}
}
void solve(int w, int fa) {
f[w][0] = 0;
f[w][1] = val[w];
for (int i=head[w];i;i=nxt[i]) if (to[i] && to[i] != fa) {
solve(to[i], w);
f[w][1] += f[to[i]][0];
f[w][0] += max(f[to[i]][1],f[to[i]][0]);
}
if (tag[w] == 2) {
f[w][0] = 0;
} else if (tag[w] == 3) {
f[w][1] = 0;
}
}
int main(){
n = read();
for (int i=1,t;i<=n;i++) {
val[i] = read();
if (aim[t=read()] != i) {
Add_Edge(i, t);
aim[i] = t;
}
}
for (int i=1;i<=n;i++) {
if (!tag[i]) {
LL tmp;
lb = rb = 0;
DFS(i,i);
tag[lb] = 2; tag = 3;
solve(i,i);
tmp = max(f[i][0], f[i][1]);
tag[lb] = 3; tag = 2;
solve(i,i);
tmp = max(tmp, max(f[i][0], f[i][1]));
tag[lb] = 3; tag = 3;
solve(i,i);
tmp = max(tmp, max(f[i][0], f[i][1]));
vout += tmp;
}
}
printf("%lld\n",vout);
return 0;
}
Way cool! Some very valid points! I appreciate you writing this post and also the rest of the site
is extremely good.
I got this web page from my buddy who told me on the topic
of this website and now this time I am browsing this website and reading very informative content at this
place.
Every weekend i used to pay a quick visit this web site, as i
want enjoyment, for the reason that this this web
site conations actually nice funny data too.
You really make it seem so easy with your presentation but I find
this matter to be really something which I think
I would never understand. It seems too complex and extremely broad for me.
I’m looking forward for your next post,
I’ll try to get the hang of it!
I read this post fully about the resemblance of hottest and previous technologies,
it’s remarkable article.
Hello, I do believe your website might be having browser compatibility issues.
When I take a look at your site in Safari, it looks fine but when opening in Internet Explorer, it’s
got some overlapping issues. I just wanted to provide you with a quick heads
up! Other than that, fantastic blog!
Great info. Lucky me I found your website by chance (stumbleupon).
I’ve saved it for later!
I loved as much as you will receive carried out right here.
The sketch is tasteful, your authored subject matter stylish.
nonetheless, you command get got an edginess over that you wish be delivering the following.
unwell unquestionably come more formerly again since
exactly the same nearly a lot often inside case you shield this
hike.
Thank you for some other informative web site.
Where else may just I get that kind of information written in such an ideal method?
I have a mission that I’m simply now running on, and I’ve been at the look
out for such information.
Hi! I know this is sort of off-topic but I needed to ask.
Does operating a well-established website like yours
require a large amount of work? I am brand new to operating a blog however I do write in my diary on a daily basis.
I’d like to start a blog so I will be able to share my own experience
and views online. Please let me know if you have any kind of recommendations or tips for new aspiring bloggers.
Thankyou!
Hello to all, it’s genuinely a good for me to pay a visit this web site, it contains
valuable Information.
I have been surfing online more than 3 hours today, but I never found any fascinating
article like yours. It’s pretty value enough for me. Personally, if
all webmasters and bloggers made excellent content as you probably did, the web will be much more useful than ever before.
I don’t even know how I ended up here, but I thought this post was great.
I don’t know who you are but definitely you are going to a famous blogger if you are not
already 😉 Cheers!
Hi there mates, how is all, and what you desire to say on the topic of
this article, in my view its truly remarkable designed for me.
I need to to thank you for this excellent read!! I certainly enjoyed every bit of
it. I’ve got you book marked to look at new things you post…
Hello everyone, it’s my first pay a visit at this web site,
and piece of writing is actually fruitful for me, keep up posting these types of articles.
I loved as much as you will receive carried out right here.
The sketch is tasteful, your authored material stylish.
nonetheless, you command get got an impatience over that you wish be delivering the following.
unwell unquestionably come more formerly again since exactly the same nearly a lot often inside case
you shield this increase.
Thank you for some other great post. Where else may anyone
get that kind of information in such an ideal means of writing?
I’ve a presentation next week, and I am on the look for such information.
Hello, yes this paragraph is actually good and I have learned lot of things from it about blogging.
thanks.
Hi there to all, how is all, I think every one is getting more
from this website, and your views are fastidious for new viewers.
Hey I know this is off topic but I was wondering if you knew of any widgets I
could add to my blog that automatically tweet my newest twitter updates.
I’ve been looking for a plug-in like this for quite some time and was
hoping maybe you would have some experience
with something like this. Please let me know if you run into anything.
I truly enjoy reading your blog and I look forward to your new updates.
This web site really has all of the info I needed about this subject
and didn’t know who to ask.
Hi there! Do you use Twitter? I’d like to follow you if that would be ok.
I’m definitely enjoying your blog and look forward
to new posts.
I feel this is among the so much important info for me. And i am
glad reading your article. But should observation on some basic things, The website
taste is perfect, the articles is in point of fact
nice : D. Just right process, cheers
What’s up, all the time i used to check web site posts here
in the early hours in the dawn, since i love to find out more and
more. natalielise plenty of fish
Really when someone doesn’t know then its up to other people that they will assist, so here it occurs.
I’ve been surfing on-line greater than three
hours these days, but I by no means found any interesting article
like yours. It is lovely price enough for me. In my opinion, if all site owners and bloggers made just right content material as you probably did, the net shall be
a lot more helpful than ever before.
Post writing is also a fun, if you be familiar with after
that you can write if not it is complicated to
write.
Hi there! I could have sworn I’ve been to this blog before but after reading through some of the
post I realized it’s new to me. Nonetheless, I’m definitely glad I found it and I’ll be bookmarking and
checking back often!
If you desire to obtain much from this piece of
writing then you have to apply such strategies to your won weblog.
Your style is so unique compared to other folks I
have read stuff from. Many thanks for posting when you’ve got
the opportunity, Guess I will just book mark this site.
Undeniably consider that which you said. Your favorite reason seemed to be at the internet the simplest thing to be mindful
of. I say to you, I definitely get annoyed at the same time as people think about issues that they just
do not recognise about. You managed to hit the nail upon the top as well
as defined out the whole thing with no need side effect , other people
can take a signal. Will probably be again to get more.
Thank you
Highly descriptive post, I loved that a lot.
Will there be a part 2?
I like what you guys tend to be up too. This type of clever work and exposure!
Keep up the wonderful works guys I’ve included you
guys to my personal blogroll.
Hello to every one, the contents present at this web page are really remarkable for people knowledge,
well, keep up the nice work fellows.
What i don’t understood is if truth be told how you are now not really a lot more
smartly-preferred than you may be now. You’re very intelligent.
You realize thus considerably relating to this topic, made me for my part
consider it from numerous numerous angles. Its like women and
men aren’t involved unless it is one thing to do with Lady
gaga! Your individual stuffs excellent. At all times deal with it up!
I visited multiple web sites but the audio quality for audio songs present at this
site is truly wonderful.
Hello! This is my first visit to your blog! We are a collection of volunteers and starting a new
initiative in a community in the same niche. Your blog
provided us useful information to work on. You have done a marvellous job!
I feel that is among the so much significant info for me.
And i’m happy reading your article. However wanna observation on few
basic issues, The website style is ideal, the articles is truly great : D.
Excellent activity, cheers
We’re a group of volunteers and starting a new scheme in our
community. Your website provided us with valuable information to work on. You’ve done an impressive task and our whole group will be thankful to you.
If you are going for most excellent contents like myself,
simply visit this site all the time as it gives feature contents, thanks
Hello I am so happy I found your webpage, I really
found you by error, while I was searching on Bing for something else, Anyhow I am
here now and would just like to say thanks for a tremendous post and a all round interesting blog (I also love the theme/design), I don’t have time to look over it all at the minute but I have book-marked it and also included your RSS feeds, so when I have time
I will be back to read a great deal more, Please do keep up the fantastic work.
I’m impressed, I have to admit. Seldom do
I come across a blog that’s equally educative
and interesting, and without a doubt, you’ve
hit the nail on the head. The issue is an issue that too few people are speaking intelligently about.
I’m very happy I found this in my search for something regarding
this.
Hi there, this weekend is fastidious in support of me, for the reason that this occasion i
am reading this great informative article here at my residence.
Hello! This post couldn’t be written any better!
Reading this post reminds me of my good old room mate!
He always kept talking about this. I will forward this page to him.
Fairly certain he will have a good read. Thank you for sharing!
Very shortly this web site will be famous among
all blogging and site-building visitors, due to it’s good posts
I know this if off topic but I’m looking into starting my own weblog and was wondering what all is required to get set up?
I’m assuming having a blog like yours would cost a pretty penny?
I’m not very web smart so I’m not 100% sure.
Any tips or advice would be greatly appreciated. Thank you
Amazing! Its in fact awesome article, I have got much clear
idea about from this piece of writing.
Hi, its pleasant paragraph about media print, we all understand media
is a enormous source of facts.
Hi there! Someone in my Facebook group shared this website with us
so I came to look it over. I’m definitely enjoying the information. I’m book-marking and will be tweeting
this to my followers! Superb blog and fantastic design and style.
What’s up to every one, it’s actually a pleasant for me to pay a
quick visit this site, it includes useful Information.
Thankfulness to my father who stated to me concerning this weblog, this weblog is
in fact amazing.
Hi there, I read your new stuff on a regular basis.
Your humoristic style is witty, keep up the good work!
It’s awesome in favor of me to have a website, which is valuable for my
experience. thanks admin
What’s up, just wanted to say, I enjoyed this post. It was practical.
Keep on posting!
It’s awesome for me to have a site, which is helpful in favor of my
knowledge. thanks admin
I have been surfing online more than 3 hours nowadays, yet I by
no means found any attention-grabbing article like yours.
It is beautiful price sufficient for me. In my opinion, if all webmasters and bloggers made
excellent content as you probably did, the internet will likely
be much more helpful than ever before.
Very good blog post. I absolutely appreciate
this website. Stick with it!
You’ve made some really good points there. I checked on the web for more information about the issue
and found most individuals will go along with your views on this site.
Today, while I was at work, my cousin stole my iphone and tested to see
if it can survive a 40 foot drop, just so she can be a youtube sensation. My apple ipad is now broken and she has 83 views.
I know this is entirely off topic but I had to share it with someone!
I’m not that much of a internet reader to be honest but your sites really nice,
keep it up! I’ll go ahead and bookmark your site to come
back in the future. All the best
Pretty! This has been a really wonderful article.
Many thanks for supplying this information.
Hi there! This blog post could not be written much better! Reading through this post reminds me of my previous roommate!
He constantly kept preaching about this. I most certainly will forward this information to
him. Pretty sure he will have a very good read. Many thanks for sharing!
Hmm it seems like your blog ate my first comment (it was super long) so I guess I’ll just sum it up what I wrote and say, I’m
thoroughly enjoying your blog. I too am an aspiring blog writer
but I’m still new to everything. Do you have any recommendations for novice blog writers?
I’d definitely appreciate it.
Hi there just wanted to give you a quick heads up.
The text in your post seem to be running
off the screen in Safari. I’m not sure if this is a format issue or something to do with internet browser compatibility but I thought I’d post to
let you know. The style and design look great though!
Hope you get the issue resolved soon. Kudos
Hello there, I found your site by way of Google even as searching for a similar matter,
your website came up, it appears to be like great.
I’ve bookmarked it in my google bookmarks.
Hello there, just become aware of your weblog thru
Google, and found that it is truly informative.
I’m going to be careful for brussels. I’ll appreciate when you continue this in future.
Many other folks shall be benefited out of your writing.
Cheers!
Very good blog! Do you have any tips for aspiring writers?
I’m planning to start my own site soon but I’m a little lost on everything.
Would you advise starting with a free platform like
Wordpress or go for a paid option? There are so many choices out
there that I’m totally overwhelmed .. Any ideas?
Thanks a lot!
Thanks for another great post. Where else may just anybody get that kind
of info in such a perfect means of writing? I have
a presentation subsequent week, and I am at the look for such
info.
Good write-up. I absolutely appreciate this website.
Stick with it!
hello!,I really like your writing so much! percentage we
be in contact more approximately your post on AOL?
I need an expert in this house to unravel my problem. Maybe that is you!
Having a look forward to peer you.
Wonderful, what a weblog it is! This web site presents helpful facts to us, keep it up.
hello there and thank you for your info – I’ve
certainly picked up something new from right here.
I did however expertise a few technical issues using this site, since I experienced
to reload the site lots of times previous to I could get it to load correctly.
I had been wondering if your hosting is OK? Not that I am complaining, but sluggish loading
instances times will very frequently affect your placement in google
and can damage your high quality score if advertising and marketing with Adwords.
Anyway I’m adding this RSS to my e-mail and could look out for a lot more
of your respective exciting content. Make sure you update this
again very soon.
I was suggested this website by my cousin. I am not sure whether this post is
written by him as no one else know such detailed about my problem.
You are amazing! Thanks!
It’s difficult to find experienced people about this subject, but you sound like you know what you’re talking about!
Thanks
You are so cool! I do not believe I’ve truly read through a
single thing like this before. So great to find someone with a few
unique thoughts on this issue. Really.. thanks for starting this up.
This site is one thing that is needed on the web, someone with a bit of originality!
Hi there 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 format
issue or something to do with browser compatibility but I thought
I’d post to let you know. The design and style look
great though! Hope you get the problem solved soon. Thanks
Great site you have got here.. It’s difficult to find high quality writing like yours these days.
I truly appreciate individuals like you! Take care!!
Thanks for the good writeup. It in reality was a leisure account it.
Glance complex to far brought agreeable from you!
By the way, how could we keep in touch?
I simply would really like to give a big thumbs up. i will always visit here.
im long time of my work I just saw very good ones and very quick to understand.kindly visit us.
congrats many likes in your blogs. I was really amazed as it was very good to read. and I want to share it with my friends knowing that they would love it too. and guys if you want more information you visit this site.thank you so much.please click this.
Hi there i am kavin, its my first occasion to commenting anywhere, when i
read this paragraph i thought i could also create comment due to
this good paragraph.
It’s awesome in favor of me to have a web page, which is valuable in favor
of my know-how. thanks admin
Pretty part of content. I simply stumbled upon your website and in accession capital to assert that I acquire in fact enjoyed account your weblog posts.
Anyway I will be subscribing in your augment or even I fulfillment
you get right of entry to consistently rapidly.
Hi to every one, the contents existing at this web page are really amazing for people experience,
well, keep up the nice work fellows.
What’s up it’s me, I am also visiting this website on a regular basis, this web page is
actually nice and the people are truly sharing fastidious thoughts.
You made some good points there. I looked on the internet for the subject matter and found most guys will go along with with your site.
It’s in fact very complex in this full of activity life to listen news on TV, so I just use world wide web for that purpose, and get the latest information.
I wanted to thank you for this great read!! I certainly
loved every little bit of it. I have got you book-marked to check
out new stuff you post…
I’m not sure where you’re getting your information, but good topic.
I needs to spend some time learning more or understanding
more. Thanks for excellent info I was looking for this info for
my mission.
I was wondering if you ever considered changing the layout of your site?
Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so people could connect with it better.
Youve got an awful lot of text for only having 1 or two images.
Maybe you could space it out better?
Magnificent items from you, man. I’ve take into account your stuff prior to and you’re just too fantastic.
I actually like what you’ve obtained right here, really like what you
are stating and the way during which you say it. You’re making it enjoyable and you continue
to take care of to stay it smart. I can not wait to learn much more from you.
This is really a great website.
Undeniably imagine that which you stated. Your favourite justification seemed
to be on the internet the easiest factor to understand of.
I say to you, I definitely get irked at the
same time as other folks think about worries that they just do not recognise about.
You managed to hit the nail upon the highest as smartly
as outlined out the whole thing with no need side-effects , folks can take
a signal. Will probably be back to get more. Thanks
I’ve been exploring for a little bit for any high quality articles or blog posts in this kind of space .
Exploring in Yahoo I ultimately stumbled upon this
site. Reading this information So i am satisfied to exhibit that
I have a very good uncanny feeling I discovered exactly what I needed.
I most certainly will make certain to don?t disregard this web site and provides it a glance regularly.
Hi! This is my first visit to your blog! We are a team
of volunteers and starting a new initiative in a community in the same niche.
Your blog provided us useful information to work on. You have done a wonderful job!
Hey there! This is kind of off topic but I need
some advice from an established blog. Is it tough to set up your own blog?
I’m not very techincal but I can figure things out pretty quick.
I’m thinking about creating my own but I’m not sure where to begin. Do you have any tips or suggestions?
With thanks
Saved as a favorite, I love your web site!
Write more, thats all I have to say. Literally, it seems as
though you relied on the video to make your point.
You definitely know what youre talking about, why throw
away your intelligence on just posting videos to your site when you could be giving us something informative to read?
It’s going to be finish of mine day, except before ending I am reading this wonderful
paragraph to improve my know-how.
That is a really good tip especially to those fresh
to the blogosphere. Short but very precise information… Many thanks for sharing
this one. A must read article!
whoah this blog is magnificent i love reading your posts. Keep up the great work! You know, lots of people are hunting around for this info, you could help them greatly.