题目分析

树上的路径路径？可以，这很点分治。

求最长的 $m$条的长度？可以，着很优先队列。

但问题是，用优先队列只能做全局才能保证复杂度是对的，但点分治是分治就不能做全局。

于是对于每次点分治，都记录下每一条从分治中心 $rt$到点 $x$的路径和其长度，将它们依次放在一个序列的末尾，以此类推继续分治。对于每一个分治中心，在处理它的时候记录下来的这些东西，两两合并可以组成一条路径。

因为已经放在序列上了，每一个元素可以去尝试组合的元素处于一个区间，问题转化为：

给定一个序列，每次可以取两个元素 $a,b$，对于每一个 $b$，$a$只能在 $[l,r]$中取，取这两个元素的价值是 $v_a+v_b$，求价值前 $m$大的数对的价值。

则转化为了超级钢琴那道题。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}

const int N=50005,KN=800005,inf=0x3f3f3f3f;
int n,m,tot,rt,mi,js,klp,krp;
int h[N],ne[N<<1],to[N<<1],w[N<<1],sz[N],vis[N];
int lp[KN],rp[KN],v[KN],Log[KN],bin[20],mxd[20][KN];

void add(int x,int y,int z) {to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
void getrt(int x,int las,int SZ) {
    sz[x]=1;int bl=0;
    for(RI i=h[x];i;i=ne[i])
        if(to[i]!=las&&!vis[to[i]])
            getrt(to[i],x,SZ),sz[x]+=sz[to[i]],bl=max(bl,sz[to[i]]);
    bl=max(bl,SZ-sz[x]);
    if(bl<mi) mi=bl,rt=x;
}
void dfs(int x,int las,int dis) {
    ++js,lp[js]=klp,rp[js]=krp,v[js]=dis;
    for(RI i=h[x];i;i=ne[i])
        if(to[i]!=las&&!vis[to[i]]) dfs(to[i],x,dis+w[i]);
}
void work(int x) {
    vis[x]=1;
    ++js,lp[js]=js,rp[js]=js-1,v[js]=0,klp=js;
    for(RI i=h[x];i;i=ne[i])
        if(!vis[to[i]]) krp=js,dfs(to[i],x,w[i]);
    for(RI i=h[x];i;i=ne[i])
        if(!vis[to[i]]) mi=inf,getrt(to[i],x,sz[to[i]]),work(rt);
}
void rmq() {
    bin[0]=1;for(RI i=1;i<=19;++i) bin[i]=bin[i-1]<<1;
    Log[0]=-1;for(RI i=1;i<=js;++i) Log[i]=Log[i>>1]+1;
    for(RI i=1;i<=js;++i) mxd[0][i]=i;
    for(RI j=1;j<=19;++j)
        for(RI i=1;i+bin[j]-1<=js;++i)
            if(v[mxd[j-1][i]]>v[mxd[j-1][i+bin[j-1]]]) mxd[j][i]=mxd[j-1][i];
            else mxd[j][i]=mxd[j-1][i+bin[j-1]];
}
int getmxd(int l,int r) {
    int t=Log[r-l+1];
    if(v[mxd[t][l]]>v[mxd[t][r-bin[t]+1]]) return mxd[t][l];
    else return mxd[t][r-bin[t]+1];
}

struct node{int l,r,x,bj,v;};
bool operator < (node A,node B) {return A.v<B.v;}
priority_queue<node> q;
int main()
{
    int x,y,z;
    n=read(),m=read();
    for(RI i=1;i<n;++i) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    mi=inf,getrt(1,0,n),work(rt),rmq();
    for(RI i=1;i<=js;++i) {
        if(lp[i]>rp[i]) continue;
        node kl;kl.l=lp[i],kl.r=rp[i],kl.x=i,kl.bj=getmxd(lp[i],rp[i]);
        kl.v=v[i]+v[kl.bj],q.push(kl);
    }
    for(RI i=1;i<=m;++i) {
        node kl=q.top();q.pop();
        if(kl.l<kl.bj) {
            node kkl;kkl.l=kl.l,kkl.r=kl.bj-1,kkl.x=kl.x;
            kkl.bj=getmxd(kkl.l,kkl.r),kkl.v=v[kkl.x]+v[kkl.bj],q.push(kkl);
        }
        if(kl.bj<kl.r) {
            node kkl;kkl.l=kl.bj+1,kkl.r=kl.r,kkl.x=kl.x;
            kkl.bj=getmxd(kkl.l,kkl.r),kkl.v=v[kkl.x]+v[kkl.bj],q.push(kkl);
        }
        printf("%d\n",kl.v);
    }
    return 0;
}