问题描述:
一棵树有 n 个点，n -1 条边，所有边长都为 1。给出一个距离 k，查询有多少对节点之间的距离不超过 k。n ≤ 10000。
| 输入样例 | 输出样例 |
| 5 4 1 2 3 1 3 1 1 4 2 3 5 1 0 0 | 8 |
静态点分布
#include <cstdio>
#include <algorithm>
#define Max 20010
#define add(u,v,w) (To[++num]=Head[u],Head[u]=num,V[num]=v,W[num]=w) // 加边
#define For(x) for (int h=Head[x],o=V[h]; h; h=To[h],o=V[h]) // 遍历树节点
#define If if (o!=fa && !f[o]) //非父节点,节点存在
#define Input for (int i=1,u,v,w; i<N; i++) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w) //建树
using namespace std;
int N,K,root,num,ans,cnt,mins,Head[Max],To[Max],V[Max],W[Max],siz[Max],dis[Max],f[Max];
/*
程序中部分变量说明
dis[i] 所有路径到 重心 的长度
siz[i] 以 i 为根节点的子树的大小(当前重心下)
f[i] i 是否还存在(分治完一次后就把重心删掉了)
cnt 记录 dis 的个数(即路径个数)
root 当前子树的重心
maxs 当前讨论的点所有子树大小中最大值(并不是全局变量，是尝试每个重心时重新开的一个变量)
mins 讨论过的点的子树大小中最大的最小值(是全局变量，用来确定哪个才是重心)
w 权值
v 线段终点
To 与Head搭配使用，记录历史数值
*/
int get_size(int x,int fa){ //返回以 x 为根的子树大小，其中 x 父节点为 fa
siz[x]=1;
For(x) If
siz[x]+=get_size(o,x);
return siz[x];
}
void get_dis(int x,int d,int fa){ //x 到重心的长度为 d，之后继续 dfs
dis[++cnt]=d; //储存结点的长度不是按照正序排列的，是按照输入的路径来的
For(x) If
get_dis(o,d+W[h],x);
return;
}
void dfs_root(int x,int tot,int fa) {
//求目标子树的重心(要求除去 x 点时，它的 maxs 值最小，那么 x 就是这棵子树的重心了)，其中 tot 是这棵子树的总大小(节点个数)
int maxs=tot-siz[x]; //这棵子树中x 父亲那一支先赋给 maxs
For(x) If{
maxs=max(maxs,siz[o]); //父节点的总节点，子节点比较最大的赋值给maxs
dfs_root(o,tot,x);
}
if (maxs<mins){ //调整重心节点
mins=maxs;
root=x;
}
return;
}
int work(int x,int d) {
//返回以 x 为根的子树内长度小于等于 K 的路径数(两个端点都在子树内)
//其实 d 在这里用处只有一个，是在做减法时方便把重心的儿子节点的 dis 先弄好，你也可以在分治的时候弄，不过就稍微有点麻烦了
cnt=0;
get_dis(x,d,0);
sort(dis+1,dis+cnt+1);
int daan=0,i=1,j=cnt;
while (i<j){
while (i<j && dis[i]+dis[j]>K) j--;
daan+=j-i; //相当于选一条路径 i，另一条可以为 [i+1,j] 里任意一条路径，这样得到的两个点之间长度(经过重心的那条路径)肯定是小于等于 K 的
i++;
}
return daan;
}
void dfs(int x){ //以 x 为重心分治一下
cnt=0;
mins=Max;
get_size(x,0);
dfs_root(x,siz[x],0);
ans+=work(root,0);
f[root]=1; //删掉重心
For(root) if (!f[o]){ //注意这里是以重心开始
ans-=work(o,W[h]); //删掉重心下的子节点，重新开始算
dfs(o); //注意，这里 dis[o] 要先赋成 W[h](即它到重心的距离)
}
return;
}
int main(){
while(scanf("%d%d",&N,&K)!=EOF && N && K){ //节点数量、距离限制
Input;
dfs(1);
printf("%d\n",ans);
num=ans=0;
for (int i=1; i<=N; i++) Head[i]=f[i]=dis[i]=0; //初始化
}
return 0;
}
笔记：这几个预处理使代码很整洁，看起来很舒适。第一次找到树的重心后遍历所有经过重心的路径，保留小于等于 k 长度的路径。再分治余下的节点，余下的节点如果有子节点，就从ans中删掉该节点中的路径，再用该节点当作重心经过遍历一次，寻找更多的小于 k 长度的路径，重心节点遍历结束后就删除
版权声明：
本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/jackypigpig/article/details/69808594