XTCPC2019 Neko and tree
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=6540
题目大意
给你一棵 $n$ 个节点的树，其中有 $m$ 个点是特殊点。至少选择一个特殊点，问有多少种选法，满足任何两个选中的特殊点之间距离不超过 $k$。
题目分析
定义 $f[x][i]$ 为点 $x$ ，在子树中选择的点集中最大的深度为 $i$ 的选择方法数量。为了防止重复计数，每一棵子树，处理完信息之后要将信息合并到父亲节点上。那么对于一棵子节点 $y$ ，他对父亲节点深度为 $i$ 的贡献为选择 $y$ 中最深深度为 $i – 1$ 的点集且选择最深深度小于 $i$ 的父亲节点的其余子树的点集，或者选择最深深度为 $i$ 的父亲节点且在 $y$ 中选择最深深度小于 $i – 1$ 的点集，以及 $y$ 中选择最大深度为 $i – 1$ 且父亲节点选择最大深度为 $i$ 的子树，注意选择子树的时候一定要注意两者最深的节点距离不超过 $k$ 。选出来的所有点集都对答案有贡献，且贡献还需要合并到父亲节点中，以便下一个节点计算的时候可以访问。统计的时候可以使用前缀和进行优化。最后得到的总和即为答案。
比赛的时候很可惜，数组下标 $f[i – 1]$ 写成 $f[i]$ 了，计数的时候以为在节点为特殊节点的时候少计了一次数导致所有计数都重复计了一遍，最后三分钟发现数组下标写错了之后也没想到重复计数的全删掉。导致最后这道题没有 A 掉。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5005;
long long mod = 1e9 + 7;
int n, m, k;
vector <int> e[maxn];
bool isr[maxn];
long long f[maxn][maxn];
long long sum[maxn];
long long sumb[maxn];
long long ans = 0;
int dfs(int x, int fa){
int y;
long long a, b;
if(isr[x]){
f[x][0]++;
ans++;
}
for(auto y : e[x]){
if(y == fa)continue;
dfs(y, x);
a = 0;
b = 0;
sum[0] = f[x][0];
for(int i=1;i<=k;i++){
sum[i] = (sum[i - 1] + f[x][i]) % mod;
}
for(int i=1;i<=k;i++){
sumb[i] = (sumb[i - 1] + f[y][i - 1]) % mod;
}
for(int i=1;i<=k;i++){
ans = (ans + f[y][i - 1] * sum[min(k - i, i)] % mod + f[x][i] * sumb[min(k - i, i)] % mod - (k - i >= i ? 1 : 0) * f[x][i] * f[y][i - 1] % mod) % mod;
f[x][i] = (f[x][i] + f[y][i - 1] * sum[min(k - i, i)] % mod + f[x][i] * sumb[min(k - i, i)] % mod - (k - i >= i ? 1 : 0) * f[x][i] * f[y][i - 1] % mod) % mod;
f[x][i] = (f[x][i] + f[y][i - 1]) % mod;
}
}
return 0;
}
int main(){
int i, j;
int x, y;
scanf("%d%d%d", &n, &m, &k);
for(i=1;i<n;i++){
scanf("%d%d", &x, &y);
e[x].push_back(y);
e[y].push_back(x);
}
for(i=1;i<=m;i++){
scanf("%d", &x);
isr[x] = true;
}
dfs(1, -1);
printf("%lld\n", (ans % mod + mod) % mod);
return 0;
}