题意：给一棵树，n个节点，给定一个数k，求任意满足dist(a,b)<=k的点对的数量。
思路：
这道题的思路比较简单，但是细节很多。
此题可以用分治法，如何分治？
（1）如果path(a,b)不经过根，那么肯定在根的某棵子树下，递归解决。
（2）如果path(a,b)经过根，那么肯定在根的不同子树下，处理它。
怎样处理？如果知道了每棵子树中的节点到根的距离，暂且将每棵子树的节点分到每个独立的桶里。每个节点都可以和其他桶里的点组成点对，只要距离<=k的话就满足要求了。逐个算可能超时了，用个简单点的方法。在这里我们不需要知道节点是谁，只需要知道距离，所以将所有节点到根的距离取出来，排个序，用两个指针在线性复杂度就可以解决本节点下的点对统计了。
但是如何去重？因为所有子树中的节点全部都混着排序了，估计会有挺多对是在同棵子树下的节点被统计到了，这暂时不需要，这是要递归解决的，那么就要去掉这些同棵树下的点对。计算的方法都是一样的。
但是还有一种情况让你TLE，就是单链时的情况，若每次以孩子来递归下去解决，可能就不行了。但是可以发现到，计算这棵子树时，完全也不用经过根，那么不妨直接找出这棵子树中的重心作为根来解决这个子问题。复杂度主要是在排序的地方，用了找重心的方法可以保证每个点最多被排序2*logn次，所以总复杂度为O(nlogn)。
如下图，红色点为重心，红色的线为虚拟边。左图是原树，右图是分治的过程。就像是每个重心隔开了一些子树一样。
有论文可以看。
//#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=;
int n, k, root, edge_cnt, ans, num, big, vis[N];
vector<int> vect[N];
struct node
{
int from,to,len;
node(){};
node(int from,int to,int len):from(from),to(to),len (len){};
}edge[N*]; void add_edge(int from,int to,int len)
{
edge[edge_cnt]=node(from,to,len);
vect[from].push_back(edge_cnt++);
} int get_size(int t,int far)
{
int cnt=;
for(int i=; i<vect[t].size(); i++)
{
node e=edge[vect[t][i]];
if(e.to!=far&&!vis[e.to]) cnt+=get_size(e.to, t);
}
return cnt;
} int get_root(int t,int far) //求重心:root。
{
int cur=, sum=;
for(int i=; i<vect[t].size(); i++)
{
node e=edge[vect[t][i]];
if( e.to!=far && !vis[e.to] )
{
int tmp=get_root(e.to, t);
sum+=tmp;
cur=max(cur, tmp);
}
}
cur=max(cur, num-sum);
if(cur<big) big=cur, root=t; //更新root
return sum;
} vector<int> seq;
void get_all(int t,int far,int len) //获取子树t的所有节点
{
seq.push_back(len);
if(len>=k) return ; //剪枝
for(int i=; i<vect[t].size(); i++)
{
node e=edge[vect[t][i]];
if( !vis[e.to] && e.to!=far ) get_all(e.to, t, len+e.len);
}
} int cal(int t,int len) //计算子树t的内部点对。
{
seq.clear();
get_all(t, , len); //将以t为根的整棵子树的len装进去seq
sort(seq.begin(), seq.end());
int tmp=, L=, R=seq.size()-;
while( L<R )
{
if( seq[L]+seq[R]<=k ) tmp+=R-L,L++;
else R--;
}
return tmp;
} void solve(int t) //主函数
{
vis[t]=;
ans+=cal(t, ); //计算子树t的答案
for(int i=; i<vect[t].size(); i++)
{
node e=edge[vect[t][i]];
if( !vis[e.to] )
{
ans-=cal(e.to, e.len); //去重
big=INF;root=-;num=get_size(e.to, -); //用于找重心
get_root(e.to, -);
solve(root);
}
}
} void init()
{
for(int i=; i<=n; i++)vect[i].clear();
memset(vis, , sizeof(vis));
ans=edge_cnt=;
} int main()
{
//freopen("input.txt", "r", stdin);
int a,b,c;
while( scanf("%d%d",&n,&k), n+k )
{
init();
for(int i=; i<n; i++)
{
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
add_edge(b,a,c);
}
num=n;big=INF;root=-; //找重心用的。
get_root(,-); //找重心
solve( root );
printf("%d\n", ans);
}
return ;
}
AC代码