相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4753
神犇题解Ⅰ：http://blog.csdn.net/a_crazy_czy/article/details/51761871
神犇题解Ⅱ：http://blog.csdn.net/WorldWide_D/article/details/51565773
解题报告
考虑分数规划的套路的话，先二分一个值
现在问题变成了：在树上选一些点，使得点权和大于等于0
但这题还有一个奇怪的要求：一个点被选，其所有祖先必须被选
这就需要一个姿势非常奇怪的DP：
先将树搞到DFS序上去，设 $r(i)$ 表示第i个点的子树中DFS序最大的那个点
设 $f(i,j)$ 表示处理到了第$i$个点，已经选择了$j$个点
那么转移分两种：
- 选择第i+1个点：$f(i+1,j+1) = f(i+1,j+1) + f(i,j) + w_{i+1}$
- 不选择第i+1个点：$f(r(i+1)+1,j) = f(r(i+1)+1,j) + f(i,j)$
这样相当于如果不选择第$i$个点的话，就强行跳过他的子树
妙，真是太妙了！
Hey there! Do you use Twitter? I’d like to follow you if that would be ok.
I’m undoubtedly enjoying your blog and look forward to
new posts.
This post will help the internet people for
setting up new webpage or even a blog from start to end.
If some one wants expert view about blogging and site-building after that i
suggest him/her to go to see this website, Keep up the pleasant job.
Heya i am for the first time here. I came across this board and
I find It truly useful & it helped me out much. I hope to give something back and aid
others like you helped me.
It’s very straightforward to find out any matter on net as compared to textbooks,
as I found this piece of writing at this web page.
Thanks for your marvelous posting! I really enjoyed reading it,
you may be a great author.I will make sure to bookmark your
blog and will come back at some point. I want to encourage continue your great job, have
a nice weekend!
Nice post. I learn something totally new and
challenging on blogs I stumbleupon every day. It will always be useful to read through
content from other writers and use a little something from their sites.
Do you mind if I quote a couple of your articles as long as I provide credit
and sources back to your weblog? My blog is in the very same area of interest as yours and my users would
truly benefit from some of the information you present here.
Please let me know if this ok with you. Thanks a lot!
Thank you for any other excellent article. Where else could anybody get that type of info in such a perfect approach of writing?
I have a presentation next week, and I’m at the look for such information.
Hey there, I think your blog might be having browser compatibility issues. When I look at your website in Opera, it looks fine but when opening in Internet Explorer, it has some overlapping. I just wanted to give you a quick heads up! Other then that, fantastic blog!
Hi! Someone in my Facebook group shared this site
with us so I came to take a look. I’m definitely loving the information. I’m bookmarking and
will be tweeting this to my followers! Exceptional blog and superb style and design.
I’m not sure where you are getting your info, but good topic.
I needs to spend some time learning more or understanding more.
Thanks for fantastic information I was looking for this information for my
mission.
Hey! I’m at work surfing around your blog from my new iphone 4!
Just wanted to say I love reading your blog and look forward to all your posts!
Carry on the great work!
Please let me know if you’re looking for a article author for
your weblog. You have some really good articles and I feel I would be a
good asset. If you ever want to take some of the load off,
I’d really like to write some articles for your blog in exchange
for a link back to mine. Please blast me an email if interested.
Thank you!
Heya i am for the first time here. I found this board and I
in finding It really useful & it helped me out much.
I hope to present one thing again and aid others such as you aided me.
Wonderful article! We will be linking to this particularly
great content on our website. Keep up the good writing.
Thanks for a marvelous posting! I quite enjoyed reading it, you happen to be a great author.I will always bookmark your blog and definitely will come back later on. I want to encourage that you continue your great posts, have a nice day!