题目链接：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;}

codeforces 161 D. Distance in Tree（树形dp）