题目链接：http://poj.org/problem?id=1741
题意：求树上两点之间距离小于等于k的点对的数量
思路：点分治模板题，推荐一篇讲的非常好的博客：https://blog.csdn.net/qq_39553725/article/details/77542223
实现代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define inf 0x7fffffff
#define rson m+1,r,rt<<1|1
#define mid int m = (l + r) >> 1
const int M = 1e5+;
struct node{
int to,w,next;
}e[M<<];
int n,m;
int vis[M],dis[M],d[M],siz[M],f[M],cnt,head[M],sum,root,k,ans;
void init(){
cnt = ;
ans = ;
memset(head,,sizeof(head));
memset(vis,,sizeof(vis));
} void add(int u,int v,int w){
e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;
} void get_root(int u,int fa){
siz[u] = ; f[u] = ;
for(int i = head[u];i;i=e[i].next){
int v = e[i].to;
if(v!=fa&&!vis[v]){
get_root(v,u);
siz[u] += siz[v];
f[u] = max(f[u],siz[v]);
}
}
// cout<<"sum: "<<sum-siz[v]<<endl
f[u] = max(f[u],sum - siz[u]);
if(f[u] < f[root]) root = u;
return ;
} void get_dis(int u,int fa){
dis[++dis[]] = d[u];
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(v != fa&& !vis[v]){
d[v] = d[u] + e[i].w;
get_dis(v,u);
}
}
return;
} int cal(int u,int c){
d[u] = c; dis[] = ;
get_dis(u,);
sort(dis+,dis+dis[]+);
int l = ,r = dis[],sum = ;
while(l < r){
if(dis[l] + dis[r] <= k){
sum+=r-l;
l ++;
}
else r--;
}
return sum;
} void solve(int u){
ans += cal(u,);
vis[u] = ;
for(int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(!vis[v]){
ans -= cal(v,e[i].w);
sum = siz[v] ;
root = ;
get_root(v,);
solve(root);
}
}
}
int main()
{
int u,v,w;
ios::sync_with_stdio();
cin.tie(); cout.tie();
while(cin>>n>>k){
if(n==&&m==) break;
init();
for(int i = ;i <= n-;i ++){
cin>>u>>v>>w;
add(u,v,w); add(v,u,w);
}
f[] = inf;
sum = n;
root = ;
get_root(,);
solve(root);
cout<<ans<<endl;
}
return ;
}