【Codeforces 736C】Ostap and Tree

相关链接

题目传送门: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;
}

271 thoughts to “【Codeforces 736C】Ostap and Tree”

  1. 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!

  2. 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

  3. 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!

  4. 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?

  5. 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?

  6. 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

  7. 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!

  8. 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.

  9. 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

  10. 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!

  11. 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?

  12. 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.

  13. 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.

  14. 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!

  15. 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!

  16. 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!

  17. 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!

  18. 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!|

  19. 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. . . . . .|

  20. 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|

  21. 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.

  22. 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.|

Leave a Reply to Demir Leather Cancel reply

Your email address will not be published. Required fields are marked *