题目描述：

给定一个N个结点的树，结点用正整数1..N编号。每条边有一个正整数权值。用d(a,b）表示从结点a到结点b路边上经过边的权值。其中要求a<b.将这n*(n-1)/2个距离从大到小排序，输出前M个距离值。

算法标签：点分治，st表

思路：

处理出点分治序后，思路跟超级钢琴是相同的，对于每一条链，确定可以与我连成一条路径的点，在点分治序上的区间，用优先队列处理每一个最大值不断二分，得到前m大

以下代码：

#include
      
       #define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=5e4+5,M=1e6;struct node{
    int l,r,pos,v,b;bool operator<(const node&t1)const{
    return v
       
         q;int rt,sz[N],son[N],size,mx[M][20],L,R,m1,m2,dist[M],Lg[M];bool vis[N];il int read(){
    int x;char ch;_(!);x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return x;}il void insert(int x,int y,int z){ne[++cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z;}il int Max(int x,int y){
    return dist[x]>dist[y]?x:y;}il void getrt(int x,int fa){    sz[x]=1;son[x]=0;    for(int i=head[x];i;i=ne[i]){        if(fa==to[i]||vis[to[i]])continue;        getrt(to[i],x);sz[x]+=sz[to[i]];        son[x]=max(son[x],sz[to[i]]);    }    son[x]=max(son[x],size-sz[x]);    if(son[rt]>son[x])rt=x;}il void dfs(int x,int fa,int v){    mx[++cnt][0]=cnt;dist[cnt]=v;    if(dist[m2]
        
         dist[m2]?m1:m2;    }    for(int i=head[x];i;i=ne[i]){        if(vis[to[i]])continue;        rt=0;size=sz[to[i]];        getrt(to[i],x);solve(rt);    }}il void init(){    for(int i=2;i<=cnt;i++)Lg[i]=Lg[i>>1]+1;    for(int j=1;j<=Lg[cnt];j++)for(int i=1;i+(1<
         
          <=cnt;i++)        mx[i][j]=Max(mx[i][j-1],mx[i+(1<