树上所有路径 $\leq k$ 的个数

根 : $root$
对于每一条边 , 包含两种情况 :
$u \implies root \implies e$
$u \implies a \implies e\ , (root \not \in a)$

先考虑第一种情况
我们遍历子树 , 求出 $val\{u \implies root\}$
如果 $val\{u \implies root\}>k$ 的话 , 停止对 $u$ 子树的枚举

易得 , $u \implies root \implies e , (u \in sonA ， v \in sonB \text{ or is } root)$
也就是说这条路径存在于不同的两个子树当中 , 或者顶点为 $root$
对于顶点为 $root$ , 这个很好统计
对于前者 , 那我们对于每一个子树的遍历 , 提取 $u \implies root (u \in sonA)$ 与 $v \implies root (v \in sonB)$
最后再把自己的贡献弄上去 , 用线段树即可
复杂度 $O(n \log n)$

考虑第二种情况
我们必须要把 $root$ 抹除才能达到 $root \not \in a$ 的条件
我们可以发现 $\sum [val\{u \implies a \implies e\ \} \leq k]=\sum\limits_{son \text{ of } root} [val\{u \implies e\} \leq k] , (root \not \in a )(u,e \in tree \text{ of } son)$

所以说后面那个东西其实就是子树的答案
那我我们直接递归到子树中去就可以了
考虑到一个问题 , 如果直接递归下去 , 复杂度为 $O(n^2 \log n)$

所以要从重心下去 , 找的复杂度是 $a$ , 一共会找 $b$ 次 , $b$ 是 $n$ , 而 $a$ 平均为 $\frac n b$ , 这个东西骤于 $n$ 的。

而这个重心怎么找 ?
我们用上一次的 $size$ ,如果这家伙的 $size$ 为先前的一半(或者差不多)的话 , 就可以了

时间复杂度 $O(n \log^2 n)$ , 优秀

Const
    root=1;
    total=1000;
var
    cnt,size,tree,next,from,reach,value:array[-1..total] of longint;
    i,j,n,k,a,b,c,tot,ans:longint;
procedure Link(x,y,sum:longint);
begin
    inc(tot); from[tot]:=x; reach[tot]:=y; value[tot]:=sum;
    next[tot]:=cnt[x]; cnt[x]:=tot;
end;
function Query(l,r,k,x,y:longint):longint;
var mid:longint;
begin
    if (x<=l)and(r<=y) then exit(tree[k]); mid:=(l+r) >> 1;
    if x<=mid then inc(Query,Query(l,mid,k << 1,x,y));
    if y>mid then inc(Query,Query(mid+1,r,k << 1+1,x,y));
end;
procedure Change(l,r,k,key,add:longint);
var mid:longint;
begin
    if l=r then begin inc(tree[k],add); exit; end; mid:=(l+r) >> 1;
    if key<=mid then Change(l,mid,k << 1,key,add) else Change(mid+1,r,k << 1+1,key,add);
    tree[k]:=tree[k << 1]+tree[k << 1+1];
end;
procedure AnswerMaker(dis,x,fa:longint);
var i:longint;
begin
    if x=-1 then exit; i:=cnt[x]; 
    while i<>-1 do 
    begin
        if reach[i]<>fa then 
        begin  
            if dis+value[i]<=k then inc(ans);
            inc(ans,Query(1,n,1,0,k-(dis+value[i]))); AnswerMaker(dis+value[i],reach[i],x);
            Change(1,n,1,dis+value[i],1);
        end;
    end;
end;
procedure AnswerSweeper(dis,x,fa:longint);
var i:longint;
begin
    if x=-1 then exit; i:=cnt[x]; 
    while i<>-1 do 
    begin
        if reach[i]<>fa then 
        begin  
            if dis+value[i]<=k then inc(ans);
            AnswerMaker(dis+value[i],reach[i],x);
            Change(1,n,1,dis+value[i],-1);
        end;
    end;
end;
procedure SizeMaker(x,fa:longint);
var i:longint;
begin
    if x=-1 then exit; i:=cnt[x]; 
    if i=-1 then begin size[x]:=1; exit; end;
    while i<>-1 do 
    begin
        if reach[i]<>fa then begin SizeMaker(reach[i],x); inc(size[x],size[reach[i]]); end;
        i:=next[i];
    end;
end;
function BanlancedPoint(standard,x,fa:longint):longint;
var i:longint;
begin
    if x=-1 then exit; i:=cnt[x]; BanlancedPoint:=0;
    if abs(size[x]-standard)<=2 then exit(x) else 
    begin 
        while i<>-1 do 
        begin
            if reach[i]<>fa then BanlancedPoint:=BanlancedPoint(standard,reach[i],x);
            if BanlancedPoint<>0 then exit; i:=next[i];
        end;
    end;
end;
procedure Conquer(x:longint);
var i:longint;
begin
    if x=-1 then exit; SizeMaker(x,x); i:=cnt[x];
    while i<>-1 do begin AnswerMaker(0,reach[i],reach[i]); i:=next[i]; end; i:=cnt[x];
    while i<>-1 do begin AnswerSweeper(0,reach[i],reach[i]); i:=next[i]; end; i:=cnt[x];
    while i<>-1 do begin Conquer(BanlancedPoint(size[x] >> 1,reach[i],reach[i])); reach[i]:=-1; i:=next[i]; end;
end;
begin
    filldword(cnt,sizeof(cnt) >> 2,maxlongint << 1+1); read(n,k);
    for i:=1 to n do begin read(a,b,c); Link(a,b,c); end;
    Conquer(root); writeln(ans);
end.