相关链接
题目传送门:http://codeforces.com/contest/736/problem/C
官方题解:http://codeforces.com/blog/entry/48659
解题报告
就简单DP一下
记录子树中最深的、还未与黑点匹配的点
记录可以子树中的黑点可以向上覆盖多少
时间复杂度:$O(nm^2)$
Code
#include<bits/stdc++.h> #define LL long long #define relax(a, b, c) (a = (a + (LL)b * c) % MOD) using namespace std; const int N = 300; const int MOD = 1000000007; const int BAS = 120; int n, K, head[N], nxt[N], to[N]; int *f[N], arr_back[N][N]; inline int read() { char c = getchar(); int ret = 0, f = 1; while (c < '0' || c > '9') { f = c == '-'? -1: 1; c = getchar(); } while ('0' <= c && c <= '9') { 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; to[++E] = u; nxt[E] = head[v]; head[v] = E; } inline void DFS(int w, int fa) { static int arr1_back[N], *tmp = arr1_back + BAS; f[w][-1] = f[w][K] = 1; for (int i = head[w], t; i; i = nxt[i]) { if ((t = to[i]) != fa) { DFS(t, w); for (int j = -K; j <= K; j++) { tmp[j] = f[w][j]; f[w][j] = 0; } for (int j = -K; j <= K; j++) { for (int k = -K - 1; k < K; k++) { if (j >= 0 && k >= 0) { relax(f[w][max(j, k)], tmp[j], f[t][k + 1]); } else if ((j < 0 && k >= 0) || (j >= 0 && k < 0)) { int ge = max(j, k), le = min(j, k); if (ge + 1 >= -le) { relax(f[w][ge], tmp[j], f[t][k + 1]); } else { relax(f[w][le], tmp[j], f[t][k + 1]); } } else { relax(f[w][min(j, k)], tmp[j], f[t][k + 1]); } } } } } } int main() { n = read(); K = read(); for (int i = 1; i < n; i++) { AddEdge(read(), read()); } for (int i = 1; i <= n; i++) { f[i] = arr_back[i] + BAS; } DFS(1, 1); int ans = 0; for (int i = 0; i <= K; i++) { ans = (ans + f[1][i]) % MOD; } printf("%d\n", ans); return 0; }
I think this is a real great blog post. Awesome.
Muchos Gracias for your blog.Much thanks again. Cool.
A big thank you for your article.Really looking forward to read more. Really Cool.
Thanks for sharing, this is a fantastic article post.Thanks Again. Really Great.
Thanks for sharing, this is a fantastic blog post.Much thanks again. Want more.
I truly appreciate this blog.Really thank you! Will read on…
Muchos Gracias for your blog post.Thanks Again.
wow, awesome post.Really looking forward to read more. Really Great.
Thank you for your post.Much thanks again. Great.
Muchos Gracias for your article post.Really thank you! Awesome.
Very informative article. Fantastic.
I am so grateful for your article post. Much obliged.
Great post about this. I’m surprised to see someone so educated in the matter. I am sure my visitors will find that very useful.
Really enjoyed this article post. Really Great.
Great, thanks for sharing this blog post.Much thanks again. Much obliged.
Really informative blog article.Really thank you! Much obliged.
Awesome blog post.Really looking forward to read more. Want more.
Really informative article post.Much thanks again. Want more.
Very informative article.Really looking forward to read more. Great.
Thanks so much for the blog article.Much thanks again. Keep writing.
Thanks so much for the blog post.Really thank you! Much obliged.
Muchos Gracias for your article post.Really looking forward to read more. Cool.
Thanks-a-mundo for the blog. Want more.
Very good post.Really looking forward to read more. Want more.
Thanks a lot for the article.Really thank you! Want more.
Very good blog article.Much thanks again. Much obliged.
This is one awesome article post.Really looking forward to read more. Much obliged.
Very good blog post.Really thank you!
Fantastic blog.Much thanks again. Want more.
Thank you ever so for you blog post. Really Cool.
wow, awesome article.Much thanks again. Really Cool.
Wow, great blog post.Much thanks again. Fantastic.
Appreciate you sharing, great article. Really Cool.
Say, you got a nice blog post.Really looking forward to read more. Really Great.
Very neat article.Really thank you! Will read on…
I really liked your article post.Really thank you! Keep writing.
I think this is a real great post.Really looking forward to read more. Really Great.
Say, you got a nice post.Thanks Again. Keep writing.
Hi there! I know this is kinda off topic but I was wondering if you knew where I could
locate a captcha plugin for my comment form?
I’m using the same blog platform as yours and I’m having problems finding one?
Thanks a lot!
Really appreciate you sharing this article post.Really thank you! Want more.
I appreciate you sharing this blog article.Really looking forward to read more. Really Great.
Hello there, You have done a fantastic job. I will definitely digg
it and personally suggest to my friends. I am confident they will be benefited from this
site.
Enjoyed every bit of your blog article. Will read on…
I know this if off topic but I’m looking into starting my own blog and
was wondering 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 web smart so I’m not 100% sure. Any recommendations or advice
would be greatly appreciated. Thank you
Looking forward to reading more. Great blog post.Thanks Again. Great.
wow, awesome blog post.Really thank you! Really Great.
Wow, great post.Really looking forward to read more. Awesome.
Really enjoyed this article post.Much thanks again. Want more.
Really appreciate you sharing this blog article.Really thank you! Great.
I loved your article.Really thank you! Want more.
I really liked your blog post. Thanks Again. Really Cool.
wow, awesome blog article.Thanks Again. Great.
I appreciate you sharing this blog article.Much thanks again. Really Great.
A big thank you for your post.Really looking forward to read more. Awesome.
Looking forward to reading more. Great blog. Really Great.
Hey, thanks for the blog post.Much thanks again.
It’s an remarkable piece of writing for all the internet users; they will obtain benefit from it I am sure.
Very neat article.Thanks Again. Will read on…
Great post.Really looking forward to read more. Cool.
Incredible! This blog looks exactly like my old one!
It’s on a entirely different topic but it has pretty much the same layout and design. Great choice of
colors!
Thanks again for the blog post.Much thanks again. Want more.
Thanks for sharing, this is a fantastic article post.Much thanks again.
Please let me know if you’re looking for a article writer for
your blog. You have some really good articles and I think
I would be a good asset. If you ever want to take some of the load off, I’d
love to write some content for your blog in exchange for a link back to
mine. Please shoot me an email if interested. Many thanks!
Great, thanks for sharing this post.Much thanks again. Really Cool.
Really informative blog.Really looking forward to read more. Fantastic.
Really appreciate you sharing this article post.Really thank you! Want more.
I’m curious to find out what blog platform you’re using?
I’m having some small security issues with my latest website and I would like to find something more risk-free.
Do you have any recommendations?
Hey, thanks for the post.Really thank you! Great.
Major thankies for the article.
I loved your article post.Much thanks again. Really Cool.
Really enjoyed this blog article.Much thanks again. Cool.
Appreciate you sharing, great article.Really thank you!
Thanks a lot for the article post.Much thanks again. Much obliged.
A round of applause for your article post. Cool.
Wow, great blog.Really thank you! Awesome.
Thanks for sharing, this is a fantastic blog.Really thank you! Will read on…
Stunning quest there. What happened after?
Thanks!
Thank you for your blog article.Really thank you! Want more.
Thanks for the article.Really looking forward to read more. Keep writing.
Hey, thanks for the article.Really thank you! Really Great.
Right now it appears like WordPress is the top blogging platform out there right now.
(from what I’ve read) Is that what you’re using
on your blog?
Very good blog. Want more.
Great weblog right here! Additionally your
site so much up very fast! What host are you using?
Can I am getting your affiliate link to your host?
I wish my site loaded up as fast as yours lol
I am so grateful for your post.Much thanks again. Great.
Muchos Gracias for your post. Keep writing.
Hi! This is my first comment here so I just wanted to
give a quick shout out and say I genuinely enjoy reading your posts.
Can you suggest any other blogs/websites/forums
that cover the same topics? Thanks a lot!
I am so grateful for your blog article.Thanks Again. Cool.
Hey, thanks for the blog post.Much thanks again. Will read on…
Hmm it seems like your site 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 everything.
Do you have any helpful hints for rookie blog writers? I’d
really appreciate it.
Im thankful for the blog article. Awesome.
I’m not that much of a online 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
Thanks a lot for the post.Really thank you!
Thanks for the blog.Really looking forward to read more. Want more.
Very informative blog.Thanks Again. Will read on…
Thanks again for the article. Cool.
I cannot thank you enough for the blog.Really looking forward to read more. Really Cool.
I really liked your blog article.Thanks Again. Awesome.
Hey, thanks for the blog article.
I really liked your article post.Much thanks again.
I think this is a real great article. Really Cool.
It is appropriate time to make a few plans for the longer term and it is time to be happy. I have learn this publish and if I could I desire to recommend you some interesting issues or suggestions. Perhaps you can write subsequent articles relating to this article. I desire to learn even more issues about it!
Thanks again for the blog post.Thanks Again. Want more.
I appreciate you sharing this article post. Great.
I truly appreciate this article post.Really thank you! Really Cool.
Thank you for your blog.Really looking forward to read more. Keep writing.
Thank you for the auspicious writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from you! However,
how could we communicate?
Thanks again for the blog.Much thanks again. Cool.
A big thank you for your blog post.Thanks Again. Great.
I am so grateful for your article post.Really looking forward to read more. Awesome.
I truly appreciate this blog.Really thank you! Will read on…
I really enjoy the blog article.Really thank you! Keep writing.
Major thankies for the blog.
Muchos Gracias for your article.Much thanks again. Really Cool.
Muchos Gracias for your article post. Fantastic.
Really enjoyed this article.Much thanks again. Keep writing.
Really appreciate you sharing this post.Thanks Again. Really Cool.
Thanks again for the article.Thanks Again. Much obliged.
Major thanks for the article.Thanks Again.
Thanks again for the article.Thanks Again. Want more.
Really informative post.Really thank you! Much obliged.
Appreciate you sharing, great blog. Really Great.
A big thank you for your blog article.Really thank you! Fantastic.
Very informative blog post.Much thanks again. Really Cool.
A round of applause for your post.Really thank you! Cool.
Thanks again for the post.Thanks Again. Awesome.
Great article post.Thanks Again. Want more.
Thank you ever so for you blog article.Much thanks again. Keep writing.
Looking forward to reading more. Great article post.Thanks Again. Fantastic.
Thanks for the blog article.Much thanks again. Keep writing.
It’s hard to find experienced people for this subject, but you sound like you know what you’re talking about!
Thanks
Really appreciate you sharing this blog post.Much thanks again. Want more.
Thank you ever so for you article.Really looking forward to read more. Cool.
Really enjoyed this article.Much thanks again. Much obliged.
When some one searches for his necessary
thing, thus he/she wants to be available that in detail,
thus that thing is maintained over here.
Looking forward to reading more. Great blog article. Much obliged.
Im grateful for the blog post.Thanks Again. Cool.
Great, thanks for sharing this blog post.
I think this is a real great article post.Really thank you! Will read on…
I am not sure where you’re getting your information, but good
topic. I needs to spend some time learning much
more or understanding more. Thanks for fantastic info I was looking for this info for my mission.
Hey, thanks for the blog post.Really looking forward to read more. Much obliged.
Thank you ever so for you blog.Really looking forward to read more. Cool.
Great, thanks for sharing this post. Cool.
Thanks a lot for the article.Thanks Again. Really Cool.
Thanks-a-mundo for the article post. Much obliged.
Really informative blog article.Thanks Again. Really Cool.
Really informative blog. Keep writing.
I appreciate you sharing this blog article.
Hey, thanks for the article.Really thank you! Cool.
Hey, thanks for the article. Fantastic.
I really like and appreciate your blog article.Thanks Again. Awesome.
Very good blog article. Great.
I am so grateful for your article.Much thanks again. Really Cool.
Please let me know if you’re looking for a article author for your blog.
You have some really great posts and I believe I would be a good asset.
If you ever want to take some of the load off, I’d absolutely love to write some articles for your blog
in exchange for a link back to mine. Please shoot me an email if interested.
Kudos!
Really informative article.
Hey, thanks for the post.Really thank you! Keep writing.
It’s awesome for me to have a website, which is beneficial for my know-how.
thanks admin
Very neat blog article.Really thank you! Cool.
I am so grateful for your blog article.Thanks Again. Awesome.
I value the blog post.Really looking forward to read more. Awesome.
Thank you ever so for you post.Really looking forward to read more. Much obliged.
Appreciate you sharing, great article post. Really Great.
I appreciate you sharing this blog.Much thanks again. Want more.
Looking forward to reading more. Great blog.Thanks Again. Will read on…
I think this is a real great blog article.Really looking forward to read more. Awesome.
Really enjoyed this post.Thanks Again. Really Cool.
I value the blog.Really looking forward to read more. Keep writing.
Someone necessarily assist to make seriously posts I would state.
That is the very first time I frequented your website page and
thus far? I amazed with the research you made to create this particular put up
incredible. Excellent process!
Really informative article.Thanks Again. Will read on…
I appreciate you sharing this blog article.Really looking forward to read more. Will read on…
Thanks a lot for the blog post.Really thank you! Really Cool.
Say, you got a nice blog article. Want more.
A big thank you for your blog article.Really looking forward to read more. Great.
Thank you for your article.Thanks Again. Want more.
Very good article post.Much thanks again. Great.
A big thank you for your article post.Thanks Again. Really Cool.
Thanks so much for the blog article.Much thanks again. Really Cool.
Very informative article.Much thanks again. Will read on…
Great, thanks for sharing this blog post.Really thank you! Great.
Thanks again for the blog post.Really looking forward to read more. Really Great.
Looking forward to reading more. Great blog post.Thanks Again. Will read on…
Great blog post. Cool.
I cannot thank you enough for the blog article.Much thanks again. Awesome.
Major thanks for the article post. Cool.
Hi it’s me, I am also visiting this web site daily, this web page is really
nice and the users are really sharing nice thoughts.
I am so grateful for your blog article.Much thanks again.
It’s not my first time to visit this web page, i am visiting this
website dailly and take fastidious data from here
daily.
Major thanks for the post.Really looking forward to read more. Fantastic.
Thanks a lot for the post.Really looking forward to read more. Great.
I am so grateful for your article.Really looking forward to read more. Great.
Wow, great blog.Much thanks again. Really Great.
Im grateful for the post.Thanks Again. Will read on…
I really enjoy the blog post. Great.
Thanks for sharing, this is a fantastic article post.Thanks Again. Much obliged.
Looking forward to reading more. Great blog.Thanks Again. Keep writing.
Awesome blog article. Really Cool.
Im grateful for the blog article.Really looking forward to read more.
Hey, thanks for the blog.Thanks Again. Really Great.
A big thank you for your blog post.Really looking forward to read more.
This is one awesome article post. Keep writing.
Looking forward to reading more. Great article.Much thanks again. Much obliged.
I really like and appreciate your post.Really thank you! Cool.
Awesome blog article. Awesome.
First of all I would like to say wonderful blog! I had a quick question in which I’d like to ask if you don’t mind.
I was curious to find out how you center yourself and clear your thoughts
prior to writing. I’ve had a difficult time clearing my thoughts in getting my ideas out
there. I truly do enjoy writing however it just seems like
the first 10 to 15 minutes are usually wasted just trying to figure out how to begin. Any recommendations or
tips? Appreciate it!
Thank you for your blog. Cool.
Im obliged for the blog.Thanks Again. Great.
Thanks for the blog post.Much thanks again. Want more.
Great article.Much thanks again.
Major thankies for the blog post.Really looking forward to read more.
Im obliged for the blog article.Much thanks again. Keep writing.
Thank you for your article.Much thanks again.
It is perfect time to make some plans for the future
and it is time to be happy. I have read this post
and if I could I want to suggest you some interesting things
or advice. Maybe you can write next articles referring to this article.
I wish to read more things about it!
I couldn’t resist commenting
Muchos Gracias for your post. Great.
Thanks for sharing, this is a fantastic blog post.Really thank you! Keep writing.
Really appreciate you sharing this blog post.Really thank you! Cool.
Great, thanks for sharing this blog post.Thanks Again. Want more.
Thanks for the blog.Really looking forward to read more. Awesome.
Really informative blog article.Really looking forward to read more. Keep writing.
I think this is a real great blog post.Thanks Again. Awesome.
Fantastic blog article.Really looking forward to read more. Fantastic.
Im obliged for the blog post.Thanks Again.
I am so grateful for your post.Really thank you! Fantastic.
I really like and appreciate your blog article.Really looking forward to read more. Much obliged.
Im obliged for the blog post.Really looking forward to read more. Awesome.
Thank you ever so for you blog article.Really looking forward to read more. Really Cool.
Awesome blog.Thanks Again. Awesome.
Really appreciate you sharing this blog article.Thanks Again.
Looking forward to reading more. Great article.Really thank you! Want more.
I cannot thank you enough for the article post.Really looking forward to read more. Really Cool.
I am so grateful for your post.Really looking forward to read more. Want more.
Awesome blog. Will read on…
Keep on writing, great job!|
WOW just what I was looking for. Came here by searching for keyword|
I really like and appreciate your post.Really thank you! Fantastic.
Really enjoyed this article. Awesome.
It’s amazing designed for me to have a site, which is valuable designed for my experience. thanks admin|
Enjoyed every bit of your blog post.Really looking forward to read more. Much obliged.
I really like and appreciate your post.Thanks Again. Fantastic.
Thanks-a-mundo for the blog post.Thanks Again. Really Great.
Really informative article post.Thanks Again. Great.
Wonderful article! We are linking to this great post on our website. Keep up the good writing.|
Muchos Gracias for your article post.Really looking forward to read more. Really Cool.
Im thankful for the post.Really looking forward to read more. Keep writing.
Pretty part of content. I just stumbled upon your weblog and in accession capital to claim that I acquire in fact loved account your blog posts. Any way I’ll be subscribing to your feeds or even I success you access consistently fast.|
Thanks again for the blog article.Really thank you! Really Cool.
Hey, thanks for the blog.Really looking forward to read more. Great.
Really appreciate you sharing this blog.Really thank you! Will read on…
Thank you ever so for you article.Much thanks again. Cool.
I love what you guys are usually up too. Such clever work and exposure! Keep up the excellent works guys I’ve added you guys to blogroll.|
I am actually pleased to read this website posts which carries lots of valuable information, thanks for providing these statistics.|
wow, awesome blog article.Thanks Again. Great.
Im grateful for the blog post.Really looking forward to read more. Awesome.
Looking forward to reading more. Great blog article.Really looking forward to read more. Really Cool.
Howdy, I believe your website could be having internet browser compatibility issues. When I take a look at your website in Safari, it looks fine however, if opening in Internet Explorer, it’s got some overlapping issues. I simply wanted to give you a quick heads up! Besides that, excellent website!|
wow, awesome blog.Really thank you!
Whats up very nice site!! Guy .. Excellent .. Wonderful .. I’ll bookmark your blog and take the feeds also? I am glad to seek out numerous useful info here in the post, we want work out extra techniques on this regard, thanks for sharing. . . . . .|
Your style is so unique in comparison to other people I have read stuff from. Many thanks for posting when you have the opportunity, Guess I will just bookmark this site.|
Fantastic post.Really thank you! Will read on…
I am so grateful for your blog post.Much thanks again. Keep writing.
Very good blog.Really thank you! Fantastic.
Major thankies for the blog post.Really thank you! Fantastic.
I loved your article.Really looking forward to read more. Great.
I know this if off topic but I’m looking into starting my own blog and was curious what all is required to get setup? 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 tips or advice would be greatly appreciated. Cheers|
Muchos Gracias for your article post.Really looking forward to read more. Really Great.
Really appreciate you sharing this article post.Really thank you! Will read on…
Thanks-a-mundo for the article.Really looking forward to read more. Awesome.
Great, thanks for sharing this blog.Really thank you! Awesome.
Say, you got a nice blog.Much thanks again. Much obliged.
Hey, thanks for the post.Thanks Again. Fantastic.
Hi there, I found your web site by means of Google while searching for a related matter, your web site got here up, it appears great. I’ve bookmarked it in my google bookmarks.
It’s actually very difficult in this active life to listen news on TV, so I simply use the web for that purpose, and obtain the newest news.|