bzoj3784 树上的路径（点分治+ST表+优先队列）

Description

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

Input

第一行两个正整数N,M

下面N-1行，每行三个正整数a,b,c(a,b<=N，C<=10000)。表示结点a到结点b有一条权值为c的边。

Output

共M行，如题所述.

Sample Input

5 10
1 2 1
1 3 2
2 4 3
2 5 4

Sample Output

7
7
6
5
4
4
3
3
2
1

HINT

N<=50000,M<=Min(300000,n*(n-1) /2 )

[Submit][Status][Discuss]

分析：
树上超级钢琴
超级钢琴是在序列上寻找前k大连续区间
想要把树变成序列，首先想到的就是dfs序
我们可以点分治，维护每个结点到根结点的距离，之后在dfs序上瞎搞
然而我的思路就在这里卡住了。。。
毕竟超级钢琴有一个前缀和的形式，但是树上的dfs序并不是一个严格的前缀和

hzwer的题解：

1.二分+点分治

二分m$m$大的路径长度，得到下界以后显然是一个nlog2n$nlo{g}^{2}n$的经典点分治，加上二分的log$log$，显然比较虚。但是点分治中有一个log$log$是sort$sort$需要的，我们就可以先一次点分治把sort$sort$的结果用vector$vector$存下来，这样的话就能把总复杂度降为nlog2n$nlo{g}^{2}n$，得到m$m$大的路径最后一次点分治暴力统计路径。

2.点分治+堆

考虑超级钢琴的做法，点分治时依次扫每棵子树，若将当前子树内的点作为路径的一个端点，另一个端点可以落在一个点分治序列的区间内（之前扫过的子树），这样得出一个长度为nlogn$nlogn$的点分治序列，加上每个点所对应的区间，然后就完全转为超级钢琴的问题了

---

怎么说呢，dada的题解都比较晦涩，不是很理解
于是就出去吹了吹冷风
简单说一下自己的理解吧

点分治时，一棵一棵子树依次处理
计算出每个结点的dis$dis$
遍历整棵树，我们会得到一个dfs$dfs$序（dfs序中记录的是每个结点的dis）
对于当前子树中的每一个结点来说，ta都可以和之前处理过的子树中的结点形成路径
因此假如以该结点为路径一端，那么另一端就在之前处理过的子树的dfs$dfs$序编号中

因为ST表不支持修改，所以我们需要在点分治完成之后维护答案
记录一个四元组：(x,y,l,r)$(x,y,l,r)$
表示以x$x$为一端，最长路径的另一端是y$y$，y$y$在dfs$dfs$序中的范围是[l,r]$[l,r]$

注意数组大小

tip

可以适当的添加一些无用结点，方便计算单链

总是RE？
发现是在solve时候写错了，mmp：solve(root);

总的来说，思路清晰后还是比较好些的
板子还是要保证正确啊！

这个算法也不是很像超级钢琴吧
不过分裂区间是一个很好的启发

#include<bits/stdc++.h>

using namespace std;

const int N=50010;
const int M=2000010;
struct node{
    int y,nxt,v;
};
node way[N<<1];
int n,m,st[N],tot=0,F[N],size[N],sz,root;
int dfn[M],clo=0,dis[N],L[M],R[M],mx[M][23],lg;
bool vis[N];
struct point{
    int x,y,l,r;
    bool operator <(const point &a) const {
        return dfn[x]+dfn[y]<dfn[a.x]+dfn[a.y];
    }
    point (int xi=0,int yi=0,int li=0,int ri=0) {
        x=xi; y=yi; r=ri; l=li;
    }
};

priority_queue<point> q;

void add(int u,int w,int z) {
    tot++;way[tot].y=w;way[tot].v=z;way[tot].nxt=st[u];st[u]=tot;
    tot++;way[tot].y=u;way[tot].v=z;way[tot].nxt=st[w];st[w]=tot;
}

void findroot(int now,int fa) {
    size[now]=1;
    F[now]=0;
    for (int i=st[now];i;i=way[i].nxt)
        if (way[i].y!=fa&&!vis[way[i].y]) {
            findroot(way[i].y,now);
            size[now]+=size[way[i].y];
            F[now]=max(F[now],size[way[i].y]);
        }
    F[now]=max(F[now],sz-size[now]);
    if (F[now]<F[root]) root=now;
}

void dfs(int Li,int Ri,int now,int fa) {
    dfn[++clo]=dis[now];
    L[clo]=Li; R[clo]=Ri;
    for (int i=st[now];i;i=way[i].nxt) 
        if (way[i].y!=fa&&!vis[way[i].y]) {
            dis[way[i].y]=dis[now]+way[i].v;
            dfs(Li,Ri,way[i].y,now);
        }
}

void solve(int now) {
    vis[now]=1;
    dfn[++clo]=0; L[clo]=0; R[clo]=0;
    int Li=clo,Ri=clo;
    for (int i=st[now];i;i=way[i].nxt)
        if (!vis[way[i].y]) 
        {
            dis[way[i].y]=way[i].v;
            dfs(Li,Ri,way[i].y,now);
            Ri=clo;
        }
    for (int i=st[now];i;i=way[i].nxt)
        if (!vis[way[i].y]) 
        {
            sz=size[way[i].y]; root=0;
            findroot(way[i].y,now);
            solve(root);
        }
}

int Max(int a,int b) {
    return dfn[a]>dfn[b]? a:b;
}

void prepare() {
    lg=log(n)/log(2);
    for (int i=1;i<=clo;i++) mx[i][0]=i;
    for (int i=1;i<=lg;i++)
        for (int j=0;j<=clo&&j+(1<<i)<=clo;j++)
            mx[j][i]=Max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
}

int ask(int l,int r) {
    if (l>r) return -1;
    if (l==r) return l;
    int k=log(r-l+1)/log(2);
    return Max(mx[l][k],mx[r-(1<<k)+1][k]);
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++) {
        int u,w,z;
        scanf("%d%d%d",&u,&w,&z);
        add(u,w,z);
    }

    sz=n; F[0]=N; root=0;
    findroot(1,0);
    solve(root);

    prepare();
    for (int i=1;i<=clo;i++) {
        int y=ask(L[i],R[i]);
        if (y) q.push(point(i,y,L[i],R[i]));
    }
    for (int i=1;i<=m;i++) {
        point now=q.top(); q.pop();
        printf("%d\n",dfn[now.x]+dfn[now.y]);

        int ya=ask(now.l,now.y-1);
        int yb=ask(now.y+1,now.r);
        if (ya!=-1) q.push(point(now.x,ya,now.l,now.y-1));
        if (yb!=-1) q.push(point(now.x,yb,now.y+1,now.r));
    }
    return 0;
}