重(新)学点分治中......
普通的点分治一般这几步：
1.找重心
2.从重心开始DFS，得到信息
3.统计经过重心的路径
4.分别分治几棵子树，继续这个过程
然后是常见的(制杖的我的)一些疑问
1.这么统计不会漏吗
不会，你递归进子树的时候经过当前重心的已经统计完了，分别统计子树就行
2.这么统计不会重吗
不会，因为你进子树不会往回走(这俩都是啥问题啊。。。)
3.复杂度？
$O(n\log n)$，根据重心的性质可得
这个题把所有路径排个序然后双指针扫即可，复杂度$O(n\log n)$
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,inf=1e9;
int siz[N],vis[N],dis[N],mem[N];
int p[N],noww[*N],goal[*N],val[*N];
int n,k,c,t1,t2,t3,cnt,lp,rp,nsiz,maxx;
long long ans;
void Link(int f,int t,int v)
{
noww[++cnt]=p[f],p[f]=cnt;
goal[cnt]=t,val[cnt]=v;
}
void Mark(int nde,int fth)
{
siz[nde]=; int tmp=;
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth&&!vis[goal[i]])
{
Mark(goal[i],nde);
siz[nde]+=siz[goal[i]];
tmp=max(tmp,siz[goal[i]]);
}
tmp=max(tmp,nsiz-siz[nde]);
if(tmp<maxx) maxx=tmp,c=nde;
}
void DFS(int nde,int fth)
{
mem[++rp]=dis[nde];
for(int i=p[nde];i;i=noww[i])
if(goal[i]!=fth&&!vis[goal[i]])
{
dis[goal[i]]=dis[nde]+val[i];
DFS(goal[i],nde);
}
}
int Getans(int nde,int fir)
{
lp=,rp=,dis[nde]=fir,DFS(nde,);
long long ret=;
sort(mem+,mem++rp);
while(lp<rp)
(mem[lp]+mem[rp]<=k)?ret+=rp-lp,lp++:rp--;
return ret;
}
void PDC(int nde)
{
ans+=Getans(nde,),vis[nde]=true;
for(int i=p[nde];i;i=noww[i])
if(!vis[goal[i]])
{
ans-=Getans(goal[i],val[i]);
nsiz=siz[goal[i]],maxx=inf;
Mark(goal[i],),PDC(c);
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&t1,&t2,&t3);
Link(t1,t2,t3),Link(t2,t1,t3);
}
scanf("%d",&k),nsiz=n,maxx=inf;
Mark(,),PDC(c),printf("%lld",ans);
return ;
}