相关链接
题目传送门：http://codeforces.com/contest/815/problem/C
解题报告
这题就是考察树DP优化复杂度的一种常用技巧
考虑暴力DP的话，复杂度是：$O(n^3)$的
但如果在父亲结点那里记录一个儿子节点的子树大小的前缀和，复杂度就变成了$O(n^2)$
证明也很简单，对于任意两个结点，只会在$LCA$处产生$1$的花费
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5009;
const LL INF = 1e14;
int n, head[N], nxt[N], to[N], sz[N];
LL b, f[N][N], g[N][N], c[N], d[N], t1[N], t2[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;
}
inline void AddEdge(int u, int v) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
}
inline void relax(LL &a, LL b) {
a = a > b? b: a;
}
inline void DFS(int w) {
f[w][0] = g[w][0] = 0;
for (int i = head[w]; i; i = nxt[i]) {
DFS(to[i]);
memcpy(t1, f[w], sizeof(t1));
memcpy(t2, g[w], sizeof(t2));
for (int j = 0; j <= sz[w]; j++) {
for (int k = 0; k <= sz[to[i]]; k++) {
relax(f[w][j + k], t1[j] + f[to[i]][k]);
relax(g[w][j + k], t2[j] + g[to[i]][k]);
}
}
sz[w] += sz[to[i]];
}
sz[w]++;
for (int i = sz[w] - 1; ~i; i--) {
g[w][i + 1] = g[w][i] + c[w] - d[w];
relax(f[w][i + 1], f[w][i] + c[w]);
relax(g[w][i + 1], f[w][i + 1]);
}
g[w][0] = 0;
}
int main() {
n = read(); b = read();
c[1] = read(); d[1] = read();
for (int i = 2; i <= n; i++) {
c[i] = read(); d[i] = read();
AddEdge(read(), i);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = g[i][j] = INF;
}
}
DFS(1);
for (int i = n; ~i; i--) {
if (g[1][i] <= b) {
printf("%d\n", i);
exit(0);
}
}
return 0;
}
Howdy! Do you know if they make any plugins to protect against hackers?
I’m kinda paranoid about losing everything I’ve worked hard
on. Any suggestions?
What’s Going down i’m new to this, I stumbled upon this I have discovered It
positively useful and it has aided me out loads. I hope to contribute & assist other customers like its aided me.
Great job.
Hello! I know this is kinda off topic however I’d
figured I’d ask. Would you be interested in trading links
or maybe guest authoring a blog article or vice-versa? My blog goes over a lot of the same topics as yours and I feel we could greatly benefit from each other.
If you are interested feel free to send me an e-mail.
I look forward to hearing from you! Terrific blog by the way!
Thanks for the marvelous posting! I really enjoyed reading it, you
happen to be a great author. I will remember to bookmark
your blog and will often come back sometime soon. I want to encourage you to ultimately continue your great
writing, have a nice evening!
Hello there! This blog post couldn’t be written any better!
Going through this post reminds me of my previous roommate!
He continually kept preaching about this. I’ll send this post to him.
Pretty sure he will have a very good read. Thanks for sharing!
An impressive share! I have just forwarded this onto a coworker who was conducting a little homework
on this. And he actually bought me dinner because I discovered it for him…
lol. So allow me to reword this…. Thanks for the meal!!
But yeah, thanks for spending the time to discuss this topic here
on your internet site.
Hi there! I know this is kinda off topic however I’d figured
I’d ask. Would you be interested in trading links or maybe guest authoring a blog post
or vice-versa? My blog addresses a lot of the same subjects as
yours and I believe we could greatly benefit from each other.
If you are interested feel free to shoot me an email.
I look forward to hearing from you! Great blog by the way!
Thanks a bunch for sharing this with all people you really understand what you’re speaking approximately!
Bookmarked. Kindly also visit my web site =). We may
have a hyperlink alternate contract among us
Hi there! This is my first visit to your blog! We are a group 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 extraordinary job!
Hmm is anyone else having problems with the images on this blog
loading? I’m trying to figure out if its a
problem on my end or if it’s the blog. Any feedback would be greatly appreciated.
I do love the manner in which you have framed this specific matter plus it does present me personally a lot of fodder for thought. Nevertheless, through everything that I have observed, I only wish as the actual remarks stack on that people today remain on point and don’t get started upon a soap box associated with the news du jour. Yet, thank you for this superb piece and while I do not agree with the idea in totality, I respect your perspective.
Superb blog you have here but I was curious if you knew of any message
boards that cover the same topics discussed here?
I’d really love to be a part of community where I can get responses from
other knowledgeable people that share the same interest.
If you have any recommendations, please let me know.
Many thanks!
Wow, awesome weblog layout! How lengthy have you ever been blogging for?
you made blogging look easy. The full glance
of your website is great, as neatly as the content
material!
I visited multiple blogs but the audio feature for audio songs present
at this web site is truly marvelous.
This site was… how do you say it? Relevant!! Finally I’ve found something that helped
me. Thanks!
Very nice post. I just stumbled upon your blog and wished to mention that I have truly enjoyed surfing around your
blog posts. After all I will be subscribing in your feed and I hope you write
once more very soon!
Thank you for the auspicious writeup. It if truth be
told was a entertainment account it. Look advanced to more introduced agreeable from you!
By the way, how could we keep up a correspondence?
Hello, just wanted to say, I liked this article.
It was funny. Keep on posting!
Link exchange is nothing else however it is only placing the other person’s web site link on your page at appropriate place and other person will
also do similar in support of you.
Magnificent beat ! I would like to apprentice
while you amend your website, how can i subscribe for a blog web site?
The account aided me a acceptable deal. I had been a little bit acquainted of
this your broadcast offered bright clear concept
Hmm it looks like your blog ate my first comment (it was extremely long) so I guess I’ll
just sum it up what I had written and say, I’m thoroughly enjoying your blog.
I too am an aspiring blog writer but I’m still new to the whole
thing. Do you have any recommendations for inexperienced blog
writers? I’d really appreciate it.
An intriguing discussion is worth comment.
There’s no doubt that that you need to write more about this topic, it might not be a taboo
subject but usually folks don’t talk about these issues.
To the next! Cheers!!
What’s up, its fastidious post about media print, we all be aware of
media is a fantastic source of facts.
Good write-up, I?¦m regular visitor of one?¦s blog, maintain up the excellent operate, and It is going to be a regular visitor for a lengthy time.