codeforces 161 D. Distance in Tree(树形dp)

时间:2022-11-11 11:37:58

题目链接:http://codeforces.com/problemset/problem/161/D

题意:给出一个树,问树上点到点的距离为k的一共有几个。

一道简单的树形dp,算是一个基础题。

设dp[i][len]表示i为根距离为len的一共有几个点。

一般的树形dp都是先dfs然后再更新dp的值,注意按这样写就行了。而且一般的树形dp都是设dp[i][k]i为根,k为条件。

void dfs(int u , int pre) {

int len = vc[u].size();

dp[u][0] = 1;

for(int i = 0 ; i < len ; i++) {

int v = vc[u][i];

if(v == pre)

continue;

dfs(v , u);

for(int j = 0 ; j < k ; j++) {

ans += dp[v][j] * dp[u][k - j - 1];

}

for(int j = 1 ; j <= k ; j++) {

dp[u][j] += dp[v][j - 1];

}

}

}

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int M = 5e4 + 10;
vector<int>vc[M];
int dp[M][510];
int n , k , x , y , ans;
void dfs(int u , int pre) {
int len = vc[u].size();
dp[u][0] = 1;
for(int i = 0 ; i < len ; i++) {
int v = vc[u][i];
if(v == pre)
continue;
dfs(v , u);
for(int j = 0 ; j < k ; j++) {
ans += dp[v][j] * dp[u][k - j - 1];
}
for(int j = 1 ; j <= k ; j++) {
dp[u][j] += dp[v][j - 1];
}
}
}
int main() {
scanf("%d%d" , &n , &k);
for(int i = 0 ; i < n - 1 ; i++) {
scanf("%d%d" , &x , &y);
vc[x].push_back(y);
vc[y].push_back(x);
}
memset(dp , 0 , sizeof(dp));
ans = 0;
dfs(1 , 0);
printf("%d\n" , ans);
return 0;
}