题目大概是，给一棵树，统计距离为k的点对数。
不会DP啊。。点分治的思路比较直观，啪啪啪敲完然后AC了。具体来说是这样的：
- 树上任何两点的路径都可以看成是一条过某棵子树根的路径，即任何一条路径都可以由一个子树到达根的一条或两条路径组成
- 就可以分治累加各个结点为根的子树的统计数目
- 对于各个子树可以这样统计：假设这个子树的根有a、b、c...若干个孩子，开一个数组cnt[i]记录有几个结点到根结点为i，依次处理a、b、c...结点及各自以下的结点，处理的时候根据当前的cnt数组统计数目，处理完后把新的数目更新到cnt数组。这样直接就能不重复地统计数目了
- 时间复杂度O(nlogn)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF (1<<30)
#define MAXN 55555
struct Edge{
int v,next;
}edge[MAXN<<];
int NE,head[MAXN];
void addEdge(int u,int v){
edge[NE].v=v; edge[NE].next=head[u];
head[u]=NE++;
}
bool vis[MAXN];
int size[MAXN];
void getSize(int u,int fa){
size[u]=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==fa || vis[v]) continue;
getSize(v,u);
size[u]+=size[v];
}
}
int cen,mini;
void getCentre(int u,int fa,int &tot){
int res=tot-size[u];
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==fa || vis[v]) continue;
getCentre(v,u,tot);
res=max(res,size[v]);
}
if(res<mini){
mini=res;
cen=u;
}
}
int getCentre(int u){
mini=INF;
getSize(u,u);
getCentre(u,u,size[u]);
return cen;
}
int n,k,cnt[],tmp[],ans;
void dfs(int u,int fa,int dist){
if(dist>k) return;
ans+=cnt[k-dist];
++tmp[dist];
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==fa || vis[v]) continue;
dfs(v,u,dist+);
}
}
void conquer(int u){
memset(cnt,,sizeof(cnt));
cnt[]=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(vis[v]) continue;
memset(tmp,,sizeof(tmp));
dfs(v,v,);
for(int i=; i<=k; ++i) cnt[i]+=tmp[i];
}
}
void divide(int u){
u=getCentre(u);
vis[u]=;
conquer(u);
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(vis[v]) continue;
divide(v);
}
}
int main(){
memset(head,-,sizeof(head));
int a,b;
scanf("%d%d",&n,&k);
for(int i=; i<n; ++i){
scanf("%d%d",&a,&b);
addEdge(a,b);
addEdge(b,a);
}
divide();
printf("%d",ans);
return ;
}