对于当前根$x$来说,有两种路径:

  1. 不经过$x$。
  2. 经过$x$。
    对于当前这一层,我们仅需处理经过$x$的路径,将不经过$x$的问题抛给$x$的子树(因为不经过$x$,则说明路径在$x$的某一棵子树上)。

那么当前这一层对于答案的贡献,也就是任意一个点$x$到根的距离与任意一个点$y$到根的距离之和小于$k$的方案数。
但是直接求合法状态很难办到,考虑所有状态减去不合法状态,不合法状态也就是两点均在在$x$的同一棵子树的方案数。
注意:记得求树的重心,保证复杂度为$O(nlog_{n}^2)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=4e4+10;
const int inf=0x3f3f3f3f;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y,d,next;}a[N<<1];int last[N],len;
void ins(int x,int y,int d){a[++len]=(edge){y,d,last[x]};last[x]=len;}
int c[N],sum,mx[N],root;bool v[N];ll d[N];
void findroot(int x,int f)
{
    c[x]=1;mx[x]=-1;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(v[y]||y==f)continue;
        findroot(y,x);c[x]+=c[y];
        if(mx[x]<c[y])mx[x]=c[y];
    }
    mx[x]=max(sum-mx[x],mx[x]);
    if(mx[root]>mx[x])root=x;
}
ll sta[N];int top,bz;
void dfs(int x,int f)
{
    if(d[x]<=bz)sta[++top]=d[x];
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(v[y]||y==f)continue;
        d[y]=d[x]+a[k].d;dfs(y,x);
    }
}
int calc(int x,int dis)
{
    d[x]=dis;top=0;dfs(x,-1);
    sort(sta+1,sta+top+1);
    int val=0;
    for(int l=1,r=top;l<r;)
    {
        if(sta[l]+sta[r]<=bz)val+=r-l,l++;//sta[l]+sta[i](l<i<=r)都是<=bz 
        else r--;// sta[l]+sta[r]>bz说明 sta[i](l<i<r)+sta[r]>bz,因此r-- 
    }
    return val;
}
ll ans;
void work(int x)
{
    ans+=calc(x,0);v[x]=1;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(v[y])continue;
        ans-=calc(y,a[k].d);
        sum=c[y];//findroot,allsize in y(tree) 
        root=0;findroot(y,0);work(root);
    }
}
int main()
{
    //freopen("a.in","r",stdin);
    int n;
    while(qr(n),qr(bz),n&&bz)
    {
        len=0;memset(last,0,sizeof(last));
        memset(v,0,sizeof(v));
        memset(mx,0,sizeof(mx));
        memset(d,0,sizeof(d));
        memset(c,0,sizeof(c));
        for(int i=1;i<n;i++)
        {
            int x,y,d;qr(x),qr(y),qr(d);
            ins(x,y,d),ins(y,x,d);
        }
        ans=0;root=0;
        sum=n;mx[0]=inf;
        findroot(1,-1);
        work(root);
        qw(ans);puts("");
    }
    return 0;
}