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

题目大意：

求出树上距离为k的点对有多少个。

思路分析：

dp[i][j] 表示 i 的子树中和 i 的距离为 j 的点数有多少个。注意dp[i] [0] 永远是1的。

然后在处理完一颗子树后，就把自身的dp 更新。

更新之前更新答案。

如果这颗子树到 i 有 x 个距离为j的。那么答案就要加上 dp[i] [ k-j-1] * x;

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define maxn 50005 using namespace std; typedef long long ll; ll dp[maxn][505]; int head[maxn]; int to[maxn<<1]; int next[maxn<<1]; int tot; int n,k; void addedge(int u,int v) { tot++; next[tot]=head[u]; to[tot]=v; head[u]=tot; } bool vis[maxn]; ll ans=0; void dfs(int x) { dp[x][0]=1; for(int p=head[x];p;p=next[p]) { if(vis[to[p]])continue; vis[to[p]]=true; dfs(to[p]); for(int i=0;i