我记得大一的时候 ，听说过楼jz的男人八题，貌似这好像是其中一题。
最近做的一个题： http://codeforces.com/contest/161/problem/D 范围: n=5e4 ,k=500 因为k 很小，所以我们可以用树形dp 解决这个问题。 dp[i][j] : i的子树 dis=j的有多少个点。 u-v dp[u][i]+=dp[v][i-1] 但是复杂度大概有n*n 不可取啊 哦，因为 k 只有500 所以我们只需要维护前500就好了。。。。
然后还有 i 到除了i 其兄弟以及兄弟子树的 dis=k，我们再用一个dfs 解决即可，不过会重复计算，我们算两遍 然后/2即可。
using namespace std; #define ll __int64 /* */ vector<int>G[50005]; ll dp[50005][505],ans; int n,k; void dfs(int u,int pre){ dp[u][0]=1; for(int i=0;i<G[u].size();i++){ int to=G[u][i]; if(to==pre) continue; dfs(to,u); for(int j=1;j<=k;j++){ dp[u][j]+=dp[to][j-1]; // printf("dfs1:%d %d %d\n",u,j,dp[u][j]); } } } void dfs2(int u,int pre){ for(int i=0;i<G[u].size();i++){ int to=G[u][i]; if(to==pre) continue; for(int j=0;j<=k;j++){ // dp[to][j] dis=j + dp[u][x] = k x=k-1-j int x=k-1-j; if(x<=0) continue; //避免和祖先重复计算 dp[u][x] -=dp[to][x-1]; //删掉属于u子树的 ans+=dp[to][j] * dp[u][x]; //兄弟之间是重复计算的 // printf("%d %d x,j :%d %d dp:%I64d %I64d\n",u,to, x,j,dp[u][x],dp[to][j]); dp[u][x] +=dp[to][x-1]; //.... } dfs2(to,u); } } int main() { //freopen("1.txt","r",stdin); scanf("%d %d",&n,&k); int u,v; for(int i=1;i<n;i++){ scanf("%d %d",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs(1,0); ans=0; for(int i=1;i<=n;i++) ans+=dp[i][k]*2; dfs2(1,0); printf("%I64d\n",ans/2); return 0; }回想起 这道题有很多变形，我打算特意找一下这道题的变形：
