如题，写的是点分治 + 李超树的 $\mathcal O(m \log n \log m)$ 做法，最慢的点跑了 3092ms，卡了好久了也没卡过 /kel

/**
 *    author: sunkuangzheng
 *    created: 11.09.2024 10:24:23
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
#pragma GCC optimize(2)
using ll = long long;
const int N = 1e6+5;
using namespace std;
int T,n,rt,tt,siz[N],vis[N],f,m,ct,u,v,wa,wb,fg; 
vector<tuple<int,int,int>> g[N]; ll a[N],b[N],ans[N],k[N],B[N]; vector<int> tp,qr[N];
#define ff for(auto [v,wa,wb] : g[u]) if(v != f && !vis[v])
struct LCT{
    int mx[N * 4],ls[N * 4],rs[N * 4],tot,rt;
    inline ll get(int id,int x){return 1ll * k[id] * x + B[id];}
    void upd(int s,int l,int r,int k){
        int mid = (l + r) / 2;
        if(get(mx[s],mid) < get(k,mid)) swap(k,mx[s]);
        if(get(mx[s],l) < get(k,l)) upd(s*2,l,mid,k);
        if(get(mx[s],r) < get(k,r)) upd(s*2+1,mid + 1,r,k);
    }inline int cmp(int a,int b,int x){return get(a,x) > get(b,x) ? a : b;}
    ll qry(int s,int l,int r,int x){
        if(l == r) return mx[s];
        int mid = (l + r) / 2;
        if(x <= mid) return cmp(mx[s],qry(s*2,l,mid,x),x);
        return cmp(mx[s],qry(s*2+1,mid+1,r,x),x);
    }inline void clr(){
        for(int i = 1;i <= ct;i ++) k[i] = B[i] = 0;
        tot = rt = ct = 0,rt = 1;
    }
}t;
void dfs1(int u,int f,int sz){
    int mx = 0; siz[u] = 1;
    ff dfs1(v,u,sz),siz[u] += siz[v],mx = max(mx,siz[v]);
    if(mx = max(mx,sz - siz[u]),mx < tt) tt = mx,rt = u;
}void dfs3(int u,int f){
    if(g[u].size() == 1) tp.push_back(u); 
    ff a[v] = a[u] + wa,b[v] = b[u] + wb,dfs3(v,u);
}void dfs5(int u,int f){fg |= qr[u].size();ff dfs5(v,u);}
void dfs2(int u){
    fg = 0,dfs5(u,0); if(!fg) return ;
    for(int _ : {0,1}){
        vis[u] = 1,t.clr(),a[u] = b[u] = 0;
        ff{
            tp.clear(),a[v] = a[u] + wa,b[v] = b[u] + wb,
            dfs3(v,u);
            for(int i : tp) for(int x : qr[i])
                ans[x] = max(ans[x],1ll * a[i] * x + b[i] + t.get(t.qry(1,0,m-1,x),x));      
            for(int i : tp) k[++ct] = a[i],B[ct] = b[i],t.upd(t.rt,0,m-1,ct);
        }reverse(g[u].begin(),g[u].end());
    }for(int x : qr[u]) ans[x] = max(ans[x],t.get(t.qry(1,0,m-1,x),x));
    ff tt = 1e9,dfs1(v,u,siz[v]),dfs2(rt);
}void dfs4(int u,int f){k[u] = a[u],B[u] = b[u],t.upd(t.rt,0,m-1,u); ff a[v] = a[u] + wa,b[v] = b[u] + wb,dfs4(v,u);}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> m;
    for(int i = 1;i < n;i ++) cin >> u >> v >> wa >> wb,g[u].emplace_back(v,wa,wb),g[v].emplace_back(u,wa,wb);
    t.rt = 1,dfs4(1,0); ct = n;
    for(int x = 0;x < m;x ++){
        int id = t.qry(t.rt,0,m-1,x);
        qr[id].push_back(x); 
    }tt = 1e9,dfs1(1,0,n),dfs2(rt);
    for(int i = 0;i < m;i ++) cout << ans[i] << " ";
}