考虑重心的定义，然后解题。
(force) (1)
暴力枚举每个点作为根节点，然后求出这个点为第一重心的方案数。
时间复杂度(O(n^2*K))
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 50010
#define mo 1000000007
#define db double
#define ll long long
#define mem(x, a) memset(x, a, sizeof x)
#define mpy(x, y) memcpy(x, y, sizeof y)
#define fo(x, a, b) for (int x = (a); x <= (b); x++)
#define fd(x, a, b) for (int x = (a); x >= (b); x--)
#define go(x) for (int p = tail[x], v; p; p = e[p].fr)
using namespace std;
struct node{int v, fr;}e[N << 1];
int n, K, tail[N], cnt = 0, val[N];
ll f[5010][510], t[510], ans = 0, ag[N];
inline int read() {
int x = 0, f = 0; char c = getchar();
while (c < '0' || c > '9') f = (c == '-') ? 1 : f, c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f ? -x : x;
}
inline void add(int u, int v) {e[++cnt] = (node){v, tail[u]}; tail[u] = cnt; ag[u]++, ag[v]++;}
void dfs(int x, int fa) {
f[x][1] = 1;
go(x) {
if ((v = e[p].v) == fa) continue;
dfs(v, x); mem(t, 0);
fd(i, K / 2, 0) {
if (f[v][i] == 0) continue;
fd(j, K - i, 0) t[i + j] = (t[i + j] + f[x][j] * f[v][i] % mo) % mo;
}
fo(i, 0, K) f[x][i] = (f[x][i] + t[i]) % mo;
}
}
void force() {
fo(i, 1, n) {
mem(f, 0), f[i][1] = 1, dfs(i, 0);
mem(f[i], 0); f[i][1] = 1;
go(i) {
v = e[p].v; mem(t, 0);
fd(j, K / 2, 0) {
if (f[v][j] == 0) continue;
if (K % 2 == 0 && j == K / 2 && v < i) continue;
fd(k, K - j, 0) t[j + k] = (t[j + k] + f[v][j] * f[i][k] % mo) % mo;
}
fo(j, 0, K) f[i][j] = (f[i][j] + t[j]) % mo;
}
ans = (ans + (ll)f[i][K] * val[i] % mo) % mo;
}
printf("%lld
", ans);
}
int main()
{
freopen("centroid.in", "r", stdin);
freopen("centroid.out", "w", stdout);
n = read(), K = read();
fo(i, 1, n) val[i] = read();
fo(i, 2, n) {
int u = read(), v = read();
add(u, v), add(v, u);
}
force();
return 0;
}
(force) (2)
我们可以进行换根操作。对于每个点求出子树连通块大小相关的(f[x][i])，以及父亲以上的连通块大小相关的(g[x][i])。
然后在换根的时候(O(K^2))修改即可。
总时间复杂度(O(n*K^2))
(Solution)
我们可以发现对于当前点为重心的话，只要它的所有儿子的子树连通块大小小于(K/2)，而当前点的子树连通块大小大于(K/2)的话，不管上面怎么选，他都必定是第一重心。
于是按照这个来设(f[x][i])表示子树连通块大小为(i)的方案数，而后设(g[x][i])表示子树中所有可能的连通块的值的和。
总时间复杂度可以证明是(O(n*K))
#include <cstdio>
#define N 50510
#define mo 1000000007
#define ll long long
#define mem(x, a) memset(x, a, sizeof x)
#define fo(x, a, b) for (int x = (a); x <= (b); x++)
#define fd(x, a, b) for (int x = (a); x >= (b); x--)
#define go(x) for (int p = tail[x], v; p; p = e[p].fr)
using namespace std;
struct node{int v, fr;}e[N << 1];
int n, K, tail[N], cnt = 0, val[N], t1[510], t2[510];
int f[N][510], g[N][510], t[510], ans = 0, siz[N], fa[N];
inline int read() {
int x = 0, f = 0; char c = getchar();
while (c < '0' || c > '9') f = (c == '-') ? 1 : f, c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f ? -x : x;
}
inline int min(int x, int y) {return x < y ? x : y;}
inline void add(int u, int v) {e[++cnt] = (node){v, tail[u]}; tail[u] = cnt;}
void dfs(int x) {
f[x][1] = 1, siz[x] = 1;
go(x) {
if ((v = e[p].v) == fa[x]) continue;
fa[v] = x, dfs(v);
// G = f * g' + f' * g
fd(i, K, 1) t[i] = t1[i] = t2[i] = 0;
fd(j, min(siz[v], K), K / 2) {
if (g[v][j] == 0) continue;
fd(i, min(siz[x], min(K - j, K / 2)), 0) t1[i + j] = (t1[i + j] + (ll)f[x][i] * g[v][j]) % mo;
}
fd(i, min(siz[v], K / 2), 1) {
if (f[v][i] == 0) continue;
fd(j, min(siz[x], K - i), K / 2) t2[i + j] = (t2[i + j] + (ll)f[v][i] * g[x][j]) % mo;
}
fd(i, min(K, siz[x] + siz[v]), K / 2) {
if (K % 2 == 1 && i == K / 2) continue;
g[x][i] = ((ll)g[x][i] + t1[i] + t2[i]) % mo;
}
// F = f * f'
fd(i, min(K / 2, siz[v]), 1) {
if (f[v][i] == 0) continue;
if ((! (K & 1)) && i == K / 2 && v < x) continue;
fd(j, min(siz[x], K - i), 1) t[i + j] = (t[i + j] + (ll)f[x][j] * f[v][i]) % mo;
}
fd(i, min(K, siz[x] + siz[v]), 1) f[x][i] = (f[x][i] + t[i]) % mo;
siz[x] += siz[v];
}
fd(i, min(siz[x], K), K / 2) {
if (f[x][i] == 0) continue;
if (K % 2 == 1 && i == K / 2) continue;
if (K % 2 == 0 && i == K / 2 && x > fa[x]) continue;
g[x][i] = (g[x][i] + (ll)f[x][i] * val[x]) % mo;
}
}
int main()
{
freopen("centroid.in", "r", stdin);
freopen("centroid.out", "w", stdout);
n = read(), K = read();
fo(i, 1, n) val[i] = read();
fo(i, 2, n) {
int u = read(), v = read();
add(u, v), add(v, u);
}
dfs(n); ans = 0;
fo(i, 1, n)
ans = (ans + g[i][K]) % mo;
printf("%d
", ans);
return 0;
}