为什么常数这么大
查看原帖
为什么常数这么大
448887
cancan123456楼主2023/7/29 22:46
#include <cstdio>
using namespace std;
#define forall(i, l, r) for (int i = l; i <= r; i++)
typedef long long ll;
const int N = 100005;
const int K = 105;
const int mod = 1000000007;
struct Edge {
	int v, next;
} edge[2 * N];
int head[N];
int cnt;
void add_edge(int u, int v) {
	cnt++;
	edge[cnt].v = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
int k, f[N][2][2][K], g[2][2][K], size[N];
// f[u][0/1][0/1][i]
// u : 当前节点.
// 0 : u 未安装.
// 1 : u 安装.
// 0 : u 未被监听.
// 1 : u 已被监听.
// i : u 子树中安装数量.
// 方案数 mod 1000000007.
int min(int a, int b) {
	return a < b ? a : b;
}
ll max(ll a, ll b) {
	return a > b ? a : b;
}
void dfs(int u, int fa) {
	size[u] = 1;
	f[u][0][0][0] = 1;
	f[u][1][0][1] = 1;
	for (int v, i = head[u]; i != 0; i = edge[i].next) {
		v = edge[i].v;
		if (v == fa) {
			continue;
		}
		dfs(v, u);
		forall(i, 0, k) {
			forall(b1, 0, 1) {
				forall(b2, 0, 1) {
					g[b1][b2][i] = 0;
				}
			}
		}
		forall(i, 0, min(size[u], k)) {
			forall(j, 0, min(k - i, size[v])) {
				forall(b1u, 0, 1) {
					forall(b2u, 0, 1) {
						forall(b1v, 0, 1) {
							forall(b2v, 0, 1) {
								if (b2v == 0 && b1u == 0) {
									continue;
								}
								int new_b1 = b1u, new_b2 = b2u | b1v;
								g[new_b1][new_b2][i + j] += (1ll * f[u][b1u][b2u][i] * f[v][b1v][b2v][j]) % mod;
								g[new_b1][new_b2][i + j] %= mod;
							}
						}
					}
				}
			}
		}
		forall(i, 0, k) {
			forall(b1, 0, 1) {
				forall(b2, 0, 1) {
					f[u][b1][b2][i] = g[b1][b2][i];
				}
			}
		}
		size[u] += size[v];
	}
//	forall(i, 0, k) {
//		forall(b1, 0, 1) {
//			forall(b2, 0, 1) {
//				printf("f[%d][%d][%d][%d] = %d\n", u, b1, b2, i, f[u][b1][b2][i]);
//			}
//		}
//	}
}
int main() {
	int n;
	scanf("%d %d", &n, &k);
	forall(i, 1, n - 1) {
		int u, v;
		scanf("%d %d", &u, &v);
		add_edge(u, v);
		add_edge(v, u);
	}
	dfs(1, 0);
	printf("%d", (f[1][0][1][k] + f[1][1][1][k]) % mod);
	return 0;
}
2023/7/29 22:46
加载中...