题目：
输入点数为N一棵树，求树上长度恰好为K的路径个数
分析：
题目的数据范围不是很紧，点分治也可以过，树形dp也可以过。这里采用点分治做法。
我们只需要单开一个类似于桶的数组，跑点分治套路，统计即可，每次处理一棵子树，先在桶上跑统计，处理完一棵子树再更新桶。这样可以保证每一段路径都直接跨过根节点内。
记得开long long。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=,M=;
struct node{int y,nxt;}e[N*];
int d[N],rt,vis[N],siz[N],c=,q[N];
int h[N],n,m,k,mx[N],sm;ll t[M],ans=;
void add(int x,int y){
e[++c]=(node){y,h[x]};h[x]=c;
} void getrt(int x,int fa){
siz[x]=;mx[x]=;
for(int i=h[x],y;i;i=e[i].nxt)
if((y=e[i].y)!=fa&&!vis[y])
getrt(y,x),siz[x]+=siz[y],
mx[x]=max(mx[x],siz[y]);
mx[x]=max(mx[x],sm-siz[x]);
if(mx[x]<mx[rt]) rt=x;return ;
} void dfs(int x,int fa){
q[++q[]]=d[x];
for(int i=h[x],y;i;i=e[i].nxt)
if((y=e[i].y)!=fa&&!vis[y])
d[y]=d[x]+,dfs(y,x);return ;
} void calc(int x){
for(int i=h[x],y;i;i=e[i].nxt)
if(!vis[y=e[i].y]){
q[]=;d[y]=;dfs(y,x);
for(int j=q[];j;j--)
if(q[j]<=k) ans+=t[k-q[j]];
for(int j=q[];j;j--)
if(q[j]<=k) t[q[j]]++;
} memset(t,,sizeof(t));
} void solve(int x){
vis[x]=;t[]=;calc(x);
for(int i=h[x],y;i;i=e[i].nxt)
if(!vis[y=e[i].y]){
sm=siz[y];mx[rt=]=N;
getrt(y,);solve(rt);
} return ;
} int main(){
scanf("%d%d",&n,&k);
for(int i=,x,y;i<n;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
mx[rt]=sm=n;getrt(,);solve(rt);
printf("%lld\n",ans);return ;
}
点分治