这明显是个淀粉质(点分治)啊

点分治入门
思路：

如果求等于K的路径条数，非常简单。

本题求小于等于K的路径条数，可以考虑改变统计答案的方法。

原本统计答案是对于一个路径长度len，判断K-len在之前的子树中出现多少次。

现在统计答案是对于一个路径长度len，判断小于等于K-len的数在之前的子树中出现多少次。

之前我们用一个桶数组f来辅助，f[i]表示i这个值是否出现过。

现在我们用树状数组维护桶数组，即可用一个log的复杂度来平衡单点修改和求前缀和的复杂度。

点分治O(logn)，枚举子树O(n)，统计答案O(logn)，由于使用树状数组，常数较小。

但是我第一次直接用memset清零树状数组，直接T飞了

所以改为记录后反向剪（居然没T，有点玄学）

参考代码

#include<bits/stdc++.h>
#define pass puts("pass")
#define LL long long
#define N 40004
using namespace std;
struct oppo {
    int to,w,next;
} rood[N*2];
int head[N],tot;
void add(int from,int to,int Long) {
    rood[++tot].to=to;
    rood[tot].w=Long;
    rood[tot].next=head[from];
    head[from]=tot;
}
int n,m,s,t,w,ask,ans,rt,sum;
int maxp[N],siz[N],rem[N],dis[N],v[5000005];
bool vis[N];
void getrt(int x,int fa) { //找重心
    siz[x]=1;
    maxp[x]=0;
    for(int i=head[x]; i; i=rood[i].next) {
        if(rood[i].to==fa||vis[rood[i].to])
            continue;
        getrt(rood[i].to,x);
        siz[x]+=siz[rood[i].to];
        maxp[x]=max(maxp[x],siz[rood[i].to]);
    }
    maxp[x]=max(maxp[x],sum-siz[x]);
    if(maxp[x]<maxp[rt]) rt=x;
}
void getdis(int x,int fa) {
    rem[++rem[0]]=dis[x];
    for(int i=head[x]; i; i=rood[i].next) {
        if(rood[i].to==fa||vis[rood[i].to])
            continue;
        dis[rood[i].to]=dis[x]+rood[i].w;
        if(dis[rood[i].to]<=ask)
            getdis(rood[i].to,x);
    }
}
void vadd(int x,int ad) {
    x++;
    for(; x<=ask+10; x+= x&(-x) ) v[x]+=ad;
}
int vask(int x) {
    x++;
    int all=0;
    for(x; x>0; x-= x&(-x) ) all+=v[x];
    return all;
}
queue<int> k;
void calc(int x) {
    vadd(0,1);
    for(int i=head[x]; i; i=rood[i].next) {
        int to=rood[i].to;
        if(vis[to]) continue;
        rem[0]=0;
        dis[to]=rood[i].w;
        getdis(to,x);
        for(int j=1; j<=rem[0]; j++)
            if(ask>=rem[j])
                ans+=vask(ask-rem[j]);
        for(int j=rem[0]; j; --j) {
            vadd(rem[j],1);
            k.push(rem[j]);
        }

    }
    while(k.size()) {
        vadd(k.front(),-1);
        k.pop();
    }
    vadd(0,-1);
}
void work(int x) {
    vis[x]=1;
    calc(x);
    for(int i=head[x]; i; i=rood[i].next) {
        if(vis[rood[i].to])
            continue;
        sum=siz[rood[i].to];
        maxp[rt=0]=N;
        getrt(rood[i].to,-1);
        getrt(rt,-1);
        work(rt);
    }
}
int main() {
    while(1) {
        ans=0;
        tot=0;
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        cin>>n>>ask;
        if(n==0)
            return 0;
        for(int i=1; i<n; i++) {
            scanf("%d%d%d",&s,&t,&w);
            add(s,t,w);
            add(t,s,w);
        }
        maxp[rt=0]=sum=n;
        getrt(1,-1);
        getrt(rt,-1);
        work(rt);
        cout<<ans<<endl;
    }
}