题目描述
给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

输入格式
N（n<=40000） 接下来n-1行边描述管道，按照题目中写的输入 接下来是k

输出格式
一行，有多少对点之间的距离小于等于k

输入输出样例
输入 #1复制
7
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2
10
输出 #1复制
5
说明/提示
k\leq 20000k≤20000 对于任意一条管道边权w_i\leq 1000w
i
​
≤1000

和统计长度为k的路径条数是一样的。

我们用树状数组维护权值前缀和即可。就能找到小于某个值的个数了。

注意：每次都要多加1，因为长度为0的必然存在。（也就是直接到根）

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
const int N=4e4+10; 
int n,k,mx,rt,sum,d[N],res,vis[N],q[N],now[N],sz[N];
int head[N],nex[N<<1],to[N<<1],w[N<<1],tot;
inline void ade(int a,int b,int c){to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;}
inline void add(int x,int v){for(;x<=k;x+=lowbit(x)) d[x]+=v;}
inline int ask(int x){int s=0; for(;x;x-=lowbit(x)) s+=d[x]; return s;}
void get(int x,int fa){
	sz[x]=1; int t=0;
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]]||to[i]==fa)	continue;
		get(to[i],x); sz[x]+=sz[to[i]]; t=max(t,sz[to[i]]);
	}
	t=max(t,sum-sz[x]); if(t<mx)	mx=t,rt=x;
}
void getdis(int x,int fa,int d){
	if(d>k)	return ;	now[++now[0]]=d;
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]]||to[i]==fa)	continue;
		getdis(to[i],x,d+w[i]);
	}
}
void solve(int x){
	q[0]=0;
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]])	continue;
		now[0]=0;	getdis(to[i],x,w[i]);
		for(int j=1;j<=now[0];j++)	res+=(ask(k-now[j]))+1;
		for(int j=1;j<=now[0];j++)
			q[++q[0]]=now[j],add(now[j],1);
	}
	for(int i=1;i<=q[0];i++)	add(q[i],-1);
}
void divide(int x){
	vis[x]=1;	solve(x);
	for(int i=head[x];i;i=nex[i]){
		if(vis[to[i]])	continue;
		mx=sum=sz[to[i]]; get(to[i],x); get(rt,x);
		divide(rt);
	}
}
signed main(){
	cin>>n;
	for(int i=1,a,b,c;i<n;i++)	scanf("%d %d %d",&a,&b,&c),ade(a,b,c),ade(b,a,c);
	cin>>k;
	mx=sum=n; get(1,0); get(rt,0); divide(rt);
	cout<<res<<endl;
	return 0;
}