【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;
}

发表评论

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