Codeforces 161D Distance in Tree(树型DP)

题目链接 Distance in Tree

$k <= 500$ 这个条件十分重要。

设$f[i][j]$为以$i$为子树,所有后代中相对深度为$j$的结点个数。

状态转移的时候,一个结点的信息由他的儿子转移过来。

那么一边进行状态转移,一边统计答案即可。

 #include <bits/stdc++.h>

 using namespace std;

 int f[][], deep[];
vector <int> v[];
int n, k, x, y;
long long ans; void dfs(int x, int fa, int dep){
int c[];
deep[x] = dep;
for (auto u : v[x]){
if (u == fa) continue;
dfs(u, x, dep + );
memset(c, , sizeof c); c[] = ;
for (int i = ; i <= k; ++i) c[i + ] = f[u][i];
for (int i = ; i <= k - ; ++i) ans += (long long)f[x][i] * c[k - i];
for (int i = ; i <= k; ++i) f[x][i] += c[i];
}
} int main(){ ans = ;
scanf("%d%d", &n, &k);
for (int i = ; i <= n - ; ++i){
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
} memset(deep, , sizeof deep);
dfs(, , );
for (int i = ; i <= n; ++i) if (deep[i] >= k) ++ans;
printf("%lld\n", ans); return ; }
上一篇:cdoj 1134 男神的约会 状压dp


下一篇:POJ 2486 Apple Tree [树状DP]