题意

给定一棵 $n$ 个点的树，边有边权。给定一个常数 $k$，定义程序 $f(u,v)$：

• 有一辆车从 $u$ 出发向 $v$ 走，油箱大小为 $k$ 且出发时满油。每经过一条边权为 $w$ 的边都使剩余油量减去 $w$。如果在点 $p$ 时发现剩余油量不足以通过下一条边，则在点 $p$ 加油把剩余油量重置为 $k$。

求在对所有有序对 $(u,v)$ 其中 $u,v\in\set{1,2,\cdots,n}$，执行 $f(u,v)$ 后，树上每个点各给几辆车加了油。

$2\le n\le 70000$，$0\le w\le k\le 10^9$，$k\ge1$。

题解

设 $u$ 的答案为 $ans_u$。因为题目本质是计算树上所有路径对点的贡献，因此考虑点分治，设当前点分中心为 $rt$，那么一条路径就可以拆成 $u\to rt\to v$，在本轮我们统计所有经过 $rt$ 的路径的贡献。

注意到，从某个点出发的车油量是 $k$，在这个点加油后车油量也是 $k$，因此对于从点 $u$ 出发的车在点 $v$ 加了油，就一定意味着所有在点 $u$ 加过油且途径点 $v$ 的车也会在 $v$ 加油。后续的求解将一直使用这个关键性质。

$\bold{u\to rt}$ 部分

此时从每个点出发的车的方向是唯一的，都是向祖先走。因此从 $u$ 出发的车，走到了某个祖先 $v\ne rt$ 处，发现没油走到 $fa_v$，那么就会在 $v$ 加一次油。根据上面的性质，所有在 $u$ 加油、目的地在 $rt$ 中 $u$ 所处的子树之外的车，也都会在 $v$ 加油。可以发现这是一个自底向上的过程，对于叶节点显然没人在它们上加油。设 $f_u$ 表示在 $u$ 的子树中，有多少个 $p$ 满足车从 $p$ 出发走到 $rt$ 和 $rt$ 的其他子树时会在 $u$ 上加油。我们用倍增算出从每个点出发走到的第一个没油的祖先 $trans_u$（当可以一路走到 $rt$ 时认为 $trans_u=0$，因为在走到 $rt$ 后是否在 $rt$ 加油还得取决于走 $rt$ 的哪个儿子），若 $trans_u\ne 0$ 则 $u$ 在统计完自己子树的贡献后，对 $trans_u$ 就有如下贡献：

• $f_{trans_u}\gets f_{trans_u}+f_u+1$；
• 设 $u$ 在 $rt$ 的孩子 $col_u$ 的子树里，$ans_{trans_u}\gets ans_{trans_u}+(f_u+1)(siz_{rt}-siz_{col_u})$。这是因为起点一共 $f_u+1$ 个，终点只要不在 $rt$ 中 $u$ 所在的子树里就会在 $trans_u$ 上加油。

这样就算完了 $u\to rt$ 的部分的贡献。由于不存在点 $u$ 的 $trans_u=rt$，所以 $rt$ 的答案只能在下个部分统计。

$\bold{rt\to v}$ 部分

仍然利用那条性质，考虑在从 $u$ 走到 $v$ 的子树中的点时因为没油而在 $fa_v$ 上加了油，这就意味着对于所有从 $col_u$ 子树外出发、终点在 $v$ 的子树里、在 $u$ 上加油的车，都会在 $v$ 上加一次油。这个性质对于 $u$ 不是 $v$ 的祖先、在 $col_v$ 子树外也适用，这启发我们对 $u$ 所处的位置也作分类讨论。

$\bold u$ 在 $\bold{col_v}$ 子树外

设 $u$ 到 $rt$ 的距离为 $dis_u$。要想满足从 $u$ 出发到 $v$ 时在 $fa_v$ 加油，需要满足：

• $dis_u+dis_v>k$ 显而易见；
• $dis_u+dis_{fa_v}\le k$ 类似上一部分，我们只考虑 $u$ 对所有从 $u$ 出发后可能的第一个加油的点的贡献。

当 $dis_v,dis_{fa_v}$ 已知时，对 $dis_u$ 的限制就是值域上的一个区间，而合法的 $u$ 带来的合法起点数就是 $f_u+1$；终点数量就是 $siz_v$，算出前者的和乘上后者就是 $v$ 对 $fa_v$ 的贡献。

$\bold u$ 是 $\bold v$ 的祖先

此时的限制是 $dis(u,v)>k, dis(u,fa_v)\le k$。可以发现合法的 $u$ 在 $v$ 的祖先链上是连续的，因此同样可以树上倍增求出顶部和底部两个点，我们记为 $abv_v$ 和 $blw_v$。对于 $abv_v\sim blw_v$ 中间的点，所有从它们出发或在它们上加油，且终点在 $v$ 子树里的车，都会在 $fa_v$ 上加一次油。设 $sum_u$ 表示对于所有终点在 $u$ 的子树里的车，会在 $u$ 及 $u$ 所有祖先处加油的起点数量。则在 dfs 到 $v$ 时，对 $fa_v$ 的贡献就是 $ans_{fa_v}\gets ans_{fa_v}+siz_v(sum_{blw_v}-sum_{fa_{abv_v}})$，为了保证终点在 $v$ 的子树里，此时有 $sum_{fa_v}=sum_{fa_{fa_v}}+sum_{blw_v}-sum_{fa_{abv_v}}$，而不是加进 $sum_{fa_v}$ 里，否则子树之间的贡献就乱了。

还有一个细节：对于在 $col_v$ 子树外的 $u$ 产生的起点也应当统计进 $sum_{fa_v}$ 里，以及你可能要对在 $col_v$ 子树里但产生的贡献做容斥。

这样就用点分治解决了这个问题，两个部分都需要树上倍增，第二个部分中统计子树外的 $u$ 的贡献不可避免的要使用带 $\log$ 的数据结构，因此时间复杂度 $O(n\log^2n)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=70005,inf=0x3f3f3f3f;
int n,k;
struct Edge{int to,nxt,val;}e[maxn<<1];int head[maxn],ecnt;
void addEdge(int u,int v,int w){e[++ecnt]=Edge{v,head[u],w},head[u]=ecnt;}

bool used[maxn];int siz[maxn],mxsiz[maxn];
void getsiz(int u,int fa){siz[u]=1;for(int i=head[u],v;i;i=e[i].nxt)if(!used[v=e[i].to]&&v!=fa)getsiz(v,u),siz[u]+=siz[v];}
void findrt(int u,int fa,int all,int&rt){
    mxsiz[u]=all-siz[u];
    for(int i=head[u],v;i;i=e[i].nxt)if(!used[v=e[i].to]&&v!=fa)findrt(v,u,all,rt),mxsiz[u]=max(mxsiz[u],siz[v]);
    if(mxsiz[u]<mxsiz[rt])rt=u;
}

int pa[maxn][20],trans[maxn];ll dis[maxn][20];
int f[maxn],col[maxn];ll ans[maxn],sum[maxn];
int blw[maxn],abv[maxn];
void prework(int u,int fa,int val,int rt,int cur_col){
    pa[u][0]=fa,f[u]=sum[u]=0,col[u]=cur_col;
    for(int i=1;i<=18;i++)pa[u][i]=pa[u][i-1]==0?0:pa[pa[u][i-1]][i-1],dis[u][i]=dis[u][i-1]+dis[pa[u][i-1]][i-1];
    ll cur=0;trans[u]=u;
    for(int i=18;~i;i--)if(pa[trans[u]][i]&&cur+dis[trans[u]][i]<=k)cur+=dis[trans[u]][i],trans[u]=pa[trans[u]][i];
    if(trans[u]==rt)trans[u]=blw[u]=abv[u]=0;
    else{
        if(cur+dis[trans[u]][0]-val>k)blw[u]=abv[u]=0;
        else{
            blw[u]=abv[u]=pa[trans[u]][0],cur=cur+dis[trans[u]][0]-val;
            for(int i=18;~i;i--)if(pa[abv[u]][i]&&cur+dis[abv[u]][i]<=k)cur+=dis[abv[u]][i],abv[u]=pa[abv[u]][i];
        }
    }for(int i=head[u],v;i;i=e[i].nxt)
        if((v=e[i].to)!=fa&&!used[v])dis[v][0]=e[i].val,prework(v,u,e[i].val,rt,cur_col?cur_col:v);
}

void dfs1(int u,int fa,int rt){// 第一部分贡献
    for(int i=head[u],v;i;i=e[i].nxt)if(!used[v=e[i].to]&&v!=fa)dfs1(v,u,rt);
    if(trans[u])f[trans[u]]+=f[u]+1,ans[trans[u]]+=(f[u]+1)*(siz[rt]-siz[col[u]]);
}

vector<pair<ll,int>>pth;
struct Table{// 对于子树外 u 的贡献我采用二分+前缀和
    vector<ll>val,sum;
    void clear(){val.clear(),sum.clear();}
    void build(){
        sort(pth.begin(),pth.end());
        for(pair<ll,int>obj:pth)val.push_back(obj.first),sum.push_back(obj.second+(sum.empty()?0:sum.back()));
    }ll ask(ll l,ll r){
        if(val.empty()||l>=val.back()||r<val.front())return 0;
        return sum[upper_bound(val.begin(),val.end(),r)-val.begin()-1]-(l<val.front()?0:sum[upper_bound(val.begin(),val.end(),l)-val.begin()-1]);
    }
}pub,prs;

void getdis(int u,int fa,ll dis){
    pth.emplace_back(dis,f[u]+1);
    for(int i=head[u],v;i;i=e[i].nxt)
        if((v=e[i].to)!=fa&&!used[v])getdis(v,u,dis+e[i].val);
}void dfs2(int u,int fa,ll dis){// 第二部分贡献
    for(int i=head[u],v;i;i=e[i].nxt)if(!used[v=e[i].to]&&v!=fa){
        ll val=0,w=e[i].val,d2=dis+w;
        if(blw[v])val+=sum[blw[v]]-(pa[abv[v]][0]?sum[pa[abv[v]][0]]:0);
        val+=pub.ask(k-d2,k-d2+w)-prs.ask(k-d2,k-d2+w);
        ans[u]+=val*siz[v],sum[u]=sum[fa]+val;
        dfs2(v,u,d2);
    }
}

void dfz(int rt){
    getsiz(rt,0),prework(rt,0,0,rt,0),dfs1(rt,0,rt);
    pub.clear(),pth.clear(),getdis(rt,0,0),pub.build();
    for(int i=head[rt],u;i;i=e[i].nxt)if(!used[u=e[i].to]){
        prs.clear(),pth.clear(),getdis(u,rt,e[i].val),prs.build();
        ll w=e[i].val,d2=w,val=pub.ask(k-d2,k-d2+w)-prs.ask(k-d2,k-d2+w);
        ans[rt]+=val*siz[u],sum[rt]=val;
        dfs2(u,rt,d2);
    }
    used[rt]=1;
    for(int i=head[rt],u;i;i=e[i].nxt)if(!used[u=e[i].to]){
        int rt1=0;getsiz(u,rt),findrt(u,rt,siz[u],rt1);
        dfz(rt1);
    }
}

int main(){
    scanf("%d%d",&n,&k),mxsiz[0]=inf;
    for(int i=1,u,v,w;i<n;i++)scanf("%d%d%d",&u,&v,&w),addEdge(++u,++v,w),addEdge(v,u,w);
    int rt=0;getsiz(1,0),findrt(1,0,n,rt),dfz(rt);
    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
    return 0;
}