题目链接：http://poj.org/problem?id=1741
给你n个点，n-1条带权值边以及数字k。要你求树上所有dis(u,v)<=k的点对，(u,v)与(v,u)视作一个。
对于这种树上路径问题我们可以采用树分治来进行处理，这里采用点分治来处理。
要求出所有dis(u,v)<=k的点对我们可以先选一点作根，求出所有经过该点且满足距离小于等于k的路径，再分别在其子树中选择一点作根，求出所有过根且满足距离小于等于k的路径，就这样一直分治下去，我们就可以求得所有dis(u,v)<=k的点对。
在点分治过程中，选点决定了点分治的复杂度，点选的不好复杂度跟O(n^2)没有差别，那么我们每次选点都是选重心，这样每次分治后树的节点数至多为分治前节点树的一半，递归的深度就是logn。在每次分治时O(n)找出所有点到根的距离，O(nlogn)快排并用双指针O(n)算出小于等于k的路径数。这样总的复杂度就是O(nlog2n)。
#include<iostream> #include<algorithm> #include<vector> using namespace std; #define maxn 100005 #define inf 0x3f3f3f3f int n,k,cnt,root,ans,maxx,head[maxn],size[maxn],son[maxn],vis[maxn]; struct edge{ int to,next,val; }e[maxn]; vector<int>dis; void add(int u,int v,int val) { e[++cnt].to=v; e[cnt].next=head[u]; e[cnt].val=val; head[u]=cnt; } void dfs_size(int u,int fa)//求各点子树大小 { size[u]=1;son[u]=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=fa&&!vis[v]) { dfs_size(v,u); size[u]+=size[v]; son[u]=max(son[u],size[v]); } } } void dfs_root(int N,int u,int fa)//求重心 { son[u]=max(son[u],N-size[u]); if(maxx>son[u]) { root=u; maxx=son[u]; } for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=fa&&!vis[v]) dfs_root(N,v,u); } } void dfs_dis(int u,int fa,int val)//求出所有点到根的距离 { dis.push_back(val); for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=fa&&!vis[v]) dfs_dis(v,u,val+e[i].val); } } int cal(int u,int val)//计算小于等于k的路径数 { dis.clear(); dfs_dis(u,0,val); sort(dis.begin(),dis.end()); int l=0,r=dis.size()-1,ret=0; while(l<r)//two-pointer { while(dis[l]+dis[r]>k&&l<r)--r; ret+=r-l; l++; } return ret; } void dfs(int u) { dfs_size(u,0); maxx=inf; dfs_root(size[u],u,0); ans+=cal(root,0);//此时算出的路径数是包括没经过这个根的路径数，后面需要减去这种的路径数 vis[root]=1;//将选的roo又被遍历t标记，防止其在之后的分治过程中 for(int i=head[root];i;i=e[i].next) { int v=e[i].to,val=e[i].val; if(!vis[v]) { ans-=cal(v,val);//子树所有边加上dis(u,v)后满足的路径数就是需要减去的路径数 dfs(v);//递归分治 } } } int main() { while(scanf("%d%d",&n,&k)&&(n+k)) { int u,v,val; for(int i=1;i<=n;i++) head[i]=vis[i]=0; cnt=ans=0; for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&val); add(u,v,val); add(v,u,val); } dfs(1); printf("%d ",ans); } return 0; }