[数据结构与算法]D. Distance in Tree（cf）树状dp

原题链接：Problem - 161D - Codeforces

题意：很简单，问你在树中有几对点之间的距离是k

解法：树状dp，从叶子节点往父节点开始推。每个父节点它的不同的子树，每次加进来一个子树就乘一遍，然后更新值，下次再乘（我说不清楚..下次画个图）

呜呜dp都好难

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))

const int N = 5e4 + 10;
const int M = 510;
vector<int> e[N];
ll dp[N][M];
ll ans = 0;
int n, k;

void dfs(int u, int pre)
{
    dp[u][0] = 1;
    for(auto i : e[u])
    {
        if(i == pre) continue;
        dfs(i, u);
        for(int j = 0; j < k; j++) ans += dp[u][j] * dp[i][k - 1- j];
        for(int j = 1; j <= k; j++) dp[u][j] += dp[i][j - 1];
    }
}

int main()
{
    scanf("%d %d", &n, &k);
    int u, v;
    rep(i, n - 1)
    {
        scanf("%d %d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    printf("%lld", ans);
    return 0;
}