트리 DP 통계 트리의 길이 K 경로 수 CodeForces 161D Distance in Tree

Distance in Tree
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
A tree is a connected graph that doesn't contain any cycles.
The distance between two vertices of a tree is the length (in edges) of the shortest path between these vertices.
You are given a tree with n vertices and a positive number k. Find the number of distinct pairs of the vertices which have a distance of exactly k between them. Note that pairs (v, u) and (u, v) are considered to be the same pair.
Input
The first line contains two integers n and k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 500) — the number of vertices and the required distance between the vertices.
Next n - 1 lines describe the edges as "ai bi"(without the quotes) (1 ≤ ai, bi ≤ n, ai ≠ bi), where ai andbi are the vertices connected by the i-th edge. All given edges are different.
Output
Print a single integer — the number of distinct pairs of the tree's vertices which have a distance of exactly k between them.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use thecin, cout streams or the %I64d specifier.
Sample test(s)
input

5 2
1 2
2 3
3 4
2 5

output

4

제목 링크:here
제목 대의: n개 노드의 나무를 제시하고 나무의 길이가 k인 경로의 줄을 통계한다(1<=n<=50000, 1<=k<=500)
뿌리 노드가 r인 나무의 경우 노드 r를 통과하고 길이가 k인 경로는 두 가지 상황으로 나눌 수 있다.
a. 노드 r는 이 경로의 단점이다.
b. 노드 r는 이 경로의 중도점이다.
우리는 변수 dp[r][k]로 r를 통과하고 길이가 k인 경로 수를 기록해도 무방하다.
dp[r][k]는 a, b 두 가지 상황의 합이다.

#include<cstdio>
#include<cstring>
#include<vector>
#define N 50005

using namespace std;

vector<int> vec[N];
int dp[N][510],ans;

void dfs(int root,int f,int x)
{
    for(int i=0;i<=x;i++) dp[root][i]=0;
    dp[root][0]=1;
    for(int i=0;i<vec[root].size();i++) {
        int son=vec[root][i];
        if(son!=f) {//              ，         dfs   
            dfs(son,root,x);
            for(int j=0;j<x;j++) ans+=dp[son][j]*dp[root][x-j-1];
            for(int j=1;j<=x;j++) dp[root][j]+=dp[son][j-1];
        }
    }
}

int main()
{
    int n,k,a,b;
    while(scanf("%d%d",&n,&k)!=EOF) {
        for(int i=0;i<n-1;i++) {
            scanf("%d%d",&a,&b);
            vec[a].push_back(b);
            vec[b].push_back(a);
        }
        ans=0;
        dfs(1,0,k);
        printf("%d
",ans);
    }
    return 0;
}