现在只过了菊花图。思路是求树上 $k$ 级祖先然后树上差分打标记，离线处理。

https://www.luogu.com.cn/paste/3p8bjccn

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,fa[21][200005],dep[500005],d[500005],sum[21][200005];
vector<pair<int,int>> Adj[200005];
void dfs(int x,int f){
    for(int i=0;i<Adj[x].size();++i){
        if(Adj[x][i].first!=f){
            dep[Adj[x][i].first]=dep[x]+1;
            fa[0][Adj[x][i].first]=x;
            sum[0][Adj[x][i].first]=Adj[x][i].second;
            dfs(Adj[x][i].first,x);
        }
    }
}
void buildfa(){
    for(int j=1;j<=20;++j){
        for(int i=1;i<=n;++i){
            fa[j][i]=fa[j-1][fa[j-1][i]];
            sum[j][i]=sum[j-1][i]+sum[j-1][fa[j-1][i]];
        }
    }
}
void add(int u,int v,int w){
    Adj[u].push_back({v,w});
    Adj[v].push_back({u,w});
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;--i){
        if(dep[fa[i][x]]>=dep[y]) x=fa[i][x];
    }
    if(x==y) return x;
    for(int i=20;i>=0;--i){
        if(fa[i][y]!=fa[i][x]) x=fa[i][x],y=fa[i][y];
    }
    return fa[0][x];
}
void cha(int x,int y){
	d[x]+=1,d[y]+=1;
	d[fa[0][lca(x,y)]]--;
	d[lca(x,y)]--;
}
void dfs1(int x,int f){
    for(int i=0;i<Adj[x].size();++i){
        if(Adj[x][i].first!=f){
            dfs1(Adj[x][i].first,x);
            d[x]+=d[Adj[x][i].first];
        }
    }
}
int dfs2(int x,int f,int dis){
	int z=1;
	for(int i=0;i<Adj[x].size();++i){
		if(Adj[x][i].first!=f){
			int w=Adj[x][i].second;
			if(w+dis<=k){
				z+=dfs2(Adj[x][i].first,x,dis+w);
			}
		}
	}
	return z;
}
signed main(){
    cin>>n>>k;
    for(int i=1,u,v,w;i<n;++i){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    dep[1]=1;
    fa[0][1]=1;
    sum[0][1]=1;
    dfs(1,0);
    buildfa();
    for(int i=1;i<=n;++i){
    	int tot=k,u=i;
    	for(int j=19;j>=0;j--){
			if(sum[j][u]<=tot){
				u=fa[j][u],tot-=sum[j][u];
			}
		}
		cha(u,i);
	}
    dfs1(1,0);
    cout<<dfs2(1,0,0)<<'\n';
    for(int i=2;i<=n;++i){
    	cout<<d[i]<<'\n';
    }
    return 0;
}