参考：

神奇的点分治序（或者叫点剖？）。就是把点分治扫过的点依次放进队列里，然后发现，对于每一棵树摊到序列上，每个点的值v是重心到这个点的距离，那么对序列上的每个点定义l为这个子树重心在序列上的位置，r为在这个重心下的当前扫的子树的前一棵被扫过的子树（天啊我在说什么），所以当前点的v+当前点的(l,r)中最大的v值就是以当前的重心为转折点接起来的两条路径，因为是r前一棵子树不会重复也不会出现计算两边同一条边的情况。

那么问题就变成了对于一个序列，前m大的“一个点值+这个点(l,r)中的最大值”。做法同bzoj 2006.

#include
    
     #include
     
      #include
      
       using namespace std;const int N=1000005;int n,m,cnt,root,mx,tot,nm,h[N],si[N],v[N],lp[N],rp[N],b[N],st[N][25];bool vis[N];struct qw{    int ne,to,va;}e[N];struct qwe{    int i,l,r,v,p;    bool operator < (const qwe &a) const    {        return v
       
        q;int read(){    int r=0,f=1;    char p=getchar();    while(p>'9'||p<'0')    {        if(p=='-')            f=-1;        p=getchar();    }    while(p>='0'&&p<='9')    {        r=r*10+p-48;        p=getchar();    }    return r*f;}int Max(int a,int b){    return v[a]>v[b]?a:b;}void ins(int i,int l,int r){    qwe now;    now.i=i,now.l=l,now.r=min(r,nm);    if(now.l>now.r)        return;    int k=b[now.r-now.l+1];    now.p=Max(st[now.l][k],st[now.r-(1<
        
         max(mxx,tot-si[u]))    {        root=u;        mx=max(mxx,tot-si[u]);    }}void getdeep(int u,int fa,int de){    v[++nm]=de;    lp[nm]=lp[nm-1];    rp[nm]=rp[nm]?rp[nm]:rp[nm-1];    for(int i=h[u];i;i=e[i].ne)        if(e[i].to!=fa&&!vis[e[i].to])            getdeep(e[i].to,u,de+e[i].va);}void dfs(int u){    vis[u]=1;    v[++nm]=0,lp[nm]=nm,rp[nm]=nm-1;    for(int i=h[u];i;i=e[i].ne)        if(!vis[e[i].to])        {            rp[nm+1]=nm;            getdeep(e[i].to,u,e[i].va);        }    for(int i=h[u];i;i=e[i].ne)        if(!vis[e[i].to])        {            tot=si[e[i].to];            mx=1<<30;            getroot(e[i].to,u);            dfs(root);        }}int main(){    n=read(),m=read();    for(int i=1;i
         
          >1]+1; for(int i=1;i<=nm;i++) st[i][0]=i; for(int j=1;(1<
          
           <=nm;j++) for(int i=1;i+(1<
           
            <=nm;i++) st[i][j]=Max(st[i][j-1],st[i+(1<