时间复杂度 $\mathcal O(n \log^4n)$，但是本题中 $n$ 仅有 $2.5 \times 10^4$，且时间限制有 $7$ 秒，理论是可以过的（？

在 LOJ 上 $n = 10000$ 的点跑了 $3$ 秒，但是 $n = 25000$ 就有一部分 T 掉了 /kel

做法是二分答案，然后点分治配合主席树检验。由于二分时需要随机选择路径检查，因此写了两两子树合并的点分治。

/**
 *    author: sunkuangzheng
 *    created: 25.04.2024 08:19:02
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5,mod = 1e9+7;
using namespace std;
mt19937_64 rd(0xaccbad);
int T,n,u,v,w,rt[N],tot,siz[N],fa[N],tt,rtt,vl[N],vis[N],f,tmp,ansu,ansv,ct,ot,ort,lu,lv,pw = 1; 
int fans; vector<int> tp;
ll k,val[N],res,lstmx,lstmn; vector<pair<int,int>> g[N]; vector<pair<vector<int>,vector<pair<int,int>>>> gr,rg,ng;
struct nd{ll x; int l,r;}t[N*30]; 
#define ff for(auto [v,w] : g[u]) if(v != f && !vis[v]) 
inline int upd(int s,int l,int r,int x){
    int p = ++tot,mid = (l + r) / 2; t[p] = t[s],t[p].x += val[x];
    if(l == r) return p; 
    if(x <= mid) return t[p].l = upd(t[p].l,l,mid,x),p;
    else return t[p].r = upd(t[p].r,mid+1,r,x),p;
}inline int cmp(int u,int v,int l,int r){
    if(t[u].x == t[v].x) return -1;
    if(l == r) return t[u].x < t[v].x;
    int mid = (l + r) / 2,d = cmp(t[u].r,t[v].r,mid+1,r);
    return (d == -1 ? cmp(t[u].l,t[v].l,l,mid) : d);
}inline int cmp2(int u,int v,int s,int l,int r){
    if(t[u].x + t[v].x == t[s].x) return -1;
    if(l == r) return t[u].x + t[v].x < t[s].x;
    int mid = (l + r) / 2,d = cmp2(t[u].r,t[v].r,t[s].r,mid+1,r);
    return (d == -1 ? cmp2(t[u].l,t[v].l,t[s].l,l,mid) : d);
}inline void dfs1(int u,int f,int sz){
    siz[u] = 1; int mx = 0;
    ff dfs1(v,u,sz),siz[u] += siz[v],mx = max(siz[v],mx);
    if(mx = max(mx,sz - siz[u]),mx < tt) tt = mx,rtt = u;
}inline void dfs3(int u,int f,vector<int> &tp){tp.push_back(u); ff rt[v] = upd(rt[u],1,n,w),dfs3(v,u,tp);}
struct dn{
    vector<int> tp;
    bool operator <(const dn &x)const{return tp.size() > x.tp.size();}
};
inline void slv(vector<int> tp,int f){
    ct = 0;
    vector<pair<int,int>> fk;
    int i = f - 1;
    for(int j = f;j < tp.size();j ++){
        while(i >= 0 && cmp2(rt[tp[i]],rt[tp[j]],ort,1,n) != 1) i --;
        res += i + 1,fk.emplace_back(i,j);
    }gr.emplace_back(tp,fk);
}inline void dfs2(int u){vis[u] = 1,tp.clear(); 
    priority_queue<dn> q; rt[u] = 0;
    dn pt; pt.tp.emplace_back(u); q.push(pt),pt.tp.clear();
    auto cmpp = [&](int x,int y){return tmp = cmp(rt[x],rt[y],1,n),(tmp == -1 ? x < y : tmp);};
    ff rt[v] = upd(0,1,n,w),dfs3(v,u,pt.tp),sort(pt.tp.begin(),pt.tp.end(),cmpp),q.push(pt),pt.tp.clear();
    while(q.size() >= 2){
        auto x = q.top().tp; q.pop(); 
        auto y = q.top().tp; q.pop();
        int now = x.size(); for(auto i : y) x.push_back(i);
        slv(x,now),inplace_merge(x.begin(),x.begin() + now,x.end(),cmpp),q.push(dn{x});
    }for(int i = ot + 1;i <= tot;i ++) t[i].x = t[i].l = t[i].r = 0; tot = ot;
    ff tt = 1e9,dfs1(v,u,siz[v]),dfs2(rtt);}
inline void dfsfa(int u,int f){fa[u] = f; ff vl[v] = w,dfsfa(v,u);}
inline void gans(int s,int l,int r){
    if(l == r) return pw = 1ll * n * pw % mod,fans = (fans + 1ll * (t[s].x / val[l]) * pw % mod) % mod,void();
    int mid = (l + r) / 2; gans(t[s].l,l,mid),gans(t[s].r,mid+1,r);
}inline void ck(int u,int v){
    int pu = u,pv = v;  //debug(u,v);
    for(int i = 0;i <= tot;i ++) t[i].x = t[i].l = t[i].r = 0;
    tot = ort = 0,fill(vis+1,vis+n+1,0),dfsfa(u,0),gr.clear();
    while(v != u) ort = upd(ort,1,n,vl[v]),v = fa[v]; 
    ot = tot,tt = 1e9,res = 0,dfs1(1,0,n),dfs2(rtt); vector<pair<int,int>> nm;
    ll tes = (res < k ? lstmx - res : res - lstmn); if(!tes) return ; //debug(res);
    ll kth = rd() % tes + 1;  
    for(int i = 0;i < gr.size();i ++){
        int fg = 0;
        auto [a,b] = gr[i];  assert(a.size() > b.size());
        nm.resize(b.size()); fill(nm.begin(),nm.end(),make_pair(-2,-1));
        auto c = (res >= k ? (ng.size() ? ng[i].second : nm) : (rg.size() ? rg[i].second : nm));
        for(int j = 0;j < b.size();j ++){
            auto [x,y] = b[j]; 
            int z = c[j].first; 
            if(z == -2 && res < k) z = a.size() - b.size() - 1; 
            if(z == -2 && res >= k) z = -1;
            if(res >= k){
                int av = x - z; 
                if(kth > av) kth -= av; else {fg = 1,lu = a[y],lv = a[x - kth + 1]; break;}
            }else{
                int av = z - x; 
                if(kth > av) kth -= av; else {fg = 1,lu = a[y],lv = a[x + kth]; break;}
            }
        }if(fg) break;
    }if(res >= k) rg = gr,lstmx = res; else lstmn = res,ng = gr,ansu = pu,ansv = pv;
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> k;
    for(int i = 1;i <= n;i ++) val[i] = rd() % (ll)(1e14);
    for(int i = 1;i < n;i ++) cin >> u >> v >> w,g[u].emplace_back(v,w),g[v].emplace_back(u,w);
    lu = rd() % n + 1,lv = rd() % n + 1,lstmx = 1ll * n * (n - 1) / 2;
    while(lv == lu) lv = rd() % n + 1;
    for(int i = 1;i <= 53;i ++) ck(lu,lv);
    for(int i = 0;i <= tot;i ++) t[i].x = t[i].l = t[i].r = 0;
    tot = ort = 0,fill(vis+1,vis+n+1,0);
    dfsfa(ansu,0); 
    while(ansv != ansu) ort = upd(ort,1,n,vl[ansv]),ansv = fa[ansv]; 
    gans(ort,1,n),cout << fans << "\n";
}

要是实在卡不了就去写边分治了 /ll