题意：给你一棵树，让你记录树上两点距离为k的点对数。 思路： dp[i][j]代表考虑i这颗子树，与它距离为j的点数量，dp[i][0]就是1了，然后dfs处理一下就可以，那么它就是答案的一部分，还有一部分就是把i当做中转节点，从u开始递归，枚举它的每个子树，ans+=(dp[u][tt]-dp[j][tt-1])*(dp[j][k-tt-1])，最后别忘记除以二，最后有点小疑惑，为什么这样就是答案了呢，会不会重复或者漏算呢，首先dp[i][k]加起来肯定是不重复的，然后画画图发现把u当做中转的也不会有重复。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50010,M=100010; int n,k; int h[N],e[M],ne[M]; int dp[N][510]; ll ans; int idx; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int fa) { dp[u][0]=1; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa) continue; dfs(j,u); for(int t=1;t<=k;t++) dp[u][t]+=dp[j][t-1]; } ans+=dp[u][k]; ll tmp=0; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa) continue; for(int t=1;k-t-1>=0;t++) tmp+=(dp[u][t]-dp[j][t-1])*(dp[j][k-t-1]); //ans+=tmp/2; } ans+=tmp/2; } int main() { cin>>n>>k; memset(h,-1,sizeof h); for(int i=0;i<n-1;i++) { int a,b; cin>>a>>b; add(a,b); add(b,a); } dfs(1,-1); // for(int i=1;i<=n;i++) // { // for(int j=0;j<=k;j++) // cout<<dp[i][j]<<' '; // cout<<endl; // } cout<<ans<<endl; return 0; }