#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; struct node { int l = 0; int r = (1<<30)-1; node* left = NULL; node* right = NULL; int sum = 0; void sons() { if(left == NULL) { left = new node; left->l = l; left->r = (l+r)/2; right = new node; right->l = (l+r)/2+1; right->r = r; } } int get_sum(int l2, int r2) { if(r2 < l || l2 > r) return 0; if(l >= l2 && r <= r2) return sum; sons(); return left->get_sum(l2,r2)+right->get_sum(l2,r2); } void add(int x, int p) { sum += p; if(l == r) return; sons(); if(x <= (l+r)/2) left->add(x,p); else right->add(x,p); } }; int n; ll K; vector<pll> graph[70001]; bool odw[70001]; ll answer[70001]; int sub[70001]; int paths[70001]; ll pref[70001]; int sub_ind[70001]; ll pref2[70001]; vector<pll> sub_paths[70001]; node segtree; void dfs_sub(int v, int pop) { sub_paths[v] = {}; sub[v] = 1; paths[v] = 1; forall(it,graph[v]) { if(!odw[it.ff] && it.ff != pop) { dfs_sub(it.ff,v); sub[v] += sub[it.ff]; } } } vi ls; vi vert_ls; void dfs_paths(int v, int pop, ll d) { pref[v] = d; vert_ls.pb(v); ls.pb(v); if(siz(ls) == 1) sub_ind[v] = v; else sub_ind[v] = ls[1]; forall(it,graph[v]) { if(!odw[it.ff] && it.ff != pop) dfs_paths(it.ff,v,d+it.ss); } int l = 0; int r = siz(ls)-2; int ans = -1; while(l <= r) { int mid = (l+r)/2; if(pref[v]-pref[ls[mid]] > K) { ans = mid; l = mid+1; } else { r = mid-1; } } if(v != pop) { if(ans != -1) paths[ls[ans+1]] += paths[v]; else sub_paths[ls[1]].pb({d,paths[v]}); } ls.pop_back(); } void dfs_ans(int v, int pop, ll cur) { ls.pb(v); forall(it,graph[v]) { if(it.ff == pop || odw[it.ff]) continue; int l = 0; int r = siz(ls)-2; int r2 = 0; while(l <= r) { int mid = (l+r)/2; if(pref[v]-pref[ls[mid]]+it.ss > K) { r2 = mid; l = mid+1; } else { r = mid-1; } } l = 0; r = r2; int l2 = r2+1; while(l <= r) { int mid = (l+r)/2; if(pref[v]-pref[ls[mid]] <= K) { l2 = mid; r = mid-1; } else { l = mid+1; } } ll ans = 0; if(l2 <= r2) { ans = pref2[ls[r2]]-pref2[ls[max(0,l2-1)]]; if(l2 == 0) { if(max(0LL,K-pref[v]-it.ss+1) <= K-pref[v]) { ans += segtree.get_sum(max(0LL,K-pref[v]-it.ss+1),K-pref[v]); if(max(0LL,K-pref[v]-it.ss+1) == 0) ans += segtree.get_sum(K-pref[sub_ind[v]]+1,K); } } } answer[v] += ans*sub[it.ff]; pref2[v] = cur+ans; dfs_ans(it.ff,v,pref2[v]); } ls.pop_back(); } void centroid(int v, ll n) { dfs_sub(v,v); int pop = v; while(true) { pii best = {0,0}; forall(it,graph[v]) { if(!odw[it.ff] && it.ff != pop) best = max(best,{sub[it.ff],it.ff}); } if(best.ff > n/2) { pop = v; v = best.ss; } else break; } odw[v] = 1; dfs_sub(v,v); vert_ls = {}; dfs_paths(v,v,0); forall(it,vert_ls) { answer[it] += (n-sub[sub_ind[it]])*paths[it]; } segtree.add(0,1); forall(it,graph[v]) { if(odw[it.ff]) continue; forall(it2,sub_paths[it.ff]) segtree.add(it2.ff,it2.ss); } ls.pb(v); pref2[v] = 0; forall(it,graph[v]) { if(odw[it.ff]) continue; forall(it2,sub_paths[it.ff]) segtree.add(it2.ff,-it2.ss); answer[v] += segtree.get_sum(K-it.ss+1,K+1)*sub[it.ff]; ll k_cnt = segtree.get_sum(K,K); dfs_ans(it.ff,v,0); forall(it2,sub_paths[it.ff]) segtree.add(it2.ff,it2.ss); } answer[v]+=n; ls.pop_back(); forall(it,graph[v]) { if(odw[it.ff]) continue; forall(it2,sub_paths[it.ff]) segtree.add(it2.ff,-it2.ss); } segtree.add(0,-1); forall(it,graph[v]) if(!odw[it.ff]) centroid(it.ff,sub[it.ff]); } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cerr.tie(0); //random_start(); cin >> n >> K; rep(i,n-1) { int a,b,c; cin >> a >> b >> c; graph[a].pb({b,c}); graph[b].pb({a,c}); } centroid(0,n); rep(i,n) cout << answer[i]-n << "\n"; }