树上的路径

题目描述

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

---

Sol

 

今天见识了一种高级东东:点分治序。

就是每次点分dfs是，同时记一个dfs序，一个点可以对应多个不同的dfs序。

考虑原先点分合并时是一棵棵子树合并上去，现在改成一个点对应一段dfs序的区间，表示这个点的链可以和这个区间合并。

然后我们把点和区间放进堆里，每次取堆顶，并把堆顶分裂成两个区间。

这个东西似乎很厉害。

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #include
             
               7 #include
              
                8 #define maxn 50005 9 using namespace std;10 int n,m,head[maxn],tot;11 int siz,f[maxn],sc,rt,vis[maxn],sz[maxn],st[maxn*20][22],w[maxn*20];12 int L[maxn*20];13 struct node{14 int v,nex,w;15 }e[maxn*2];16 struct no{17 int l,r,x,v;18 };19 bool operator <(no a,no b){20 return a.v
               
                q;23 void add(int t1,int t2,int t3){24 e[++tot].v=t2;e[tot].w=t3;e[tot].nex=head[t1];head[t1]=tot;25 }26 void findr(int k,int fa){27 f[k]=0;sz[k]=1;28 for(int i=head[k];i;i=e[i].nex){29 if(e[i].v==fa||vis[e[i].v])continue;30 findr(e[i].v,k);31 sz[k]+=sz[e[i].v];32 f[k]=max(f[k],sz[e[i].v]);33 }34 f[k]=max(f[k],siz-sz[k]);35 if(f[k]
                
                 w[b]?a:b;67 }68 int main()69 {70 cin>>n>>m;71 for(int i=1,t1,t2,t3;i
                 
                  w[b])?a:b;81 }82 for(int i=2;i<=sc;i++)L[i]=L[i/2]+1;83 while(m--){84 no t=q.top();q.pop();85 printf("%d\n",t.v);86 int p=ask(t.l,t.r);87 if(p>t.l)q.push((no){t.l,p-1,t.x,w[t.x]+w[ask(t.l,p-1)]});88 if(p