【Codeforces 736C】Ostap and Tree






#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;

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


  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!


电子邮件地址不会被公开。 必填项已用*标注