【BZOJ-3784】树上的路径 点分治 + ST + 堆

时间：2021-08-13 09:28:23

3784: 树上的路径

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit:
462  Solved: 153
[Submit][Status][Discuss]

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

Source

Solution

超级钢琴推广到树上版本

利用点分治每个点的时间戳，将树转化到序列上，顺带记录每个节点，能和他组成一条路径的左右端点L，R

然后利用超级钢琴的方法去处理就好，具体见这里

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 100010

#define MAXM 1000100

int N,M;

struct EdgeNode{int next,to,val;}edge[MAXN<<];

int head[MAXN],cnt=;

void AddEdge(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].val=w;}

void InsertEdge(int u,int v,int w) {AddEdge(u,v,w); AddEdge(v,u,w);}

int maxx[MAXN],size[MAXN],Sz,root,L[MAXM],R[MAXM],D[MAXM],pl,pr,dfn;

bool visit[MAXN];

void DFSRoot(int now,int last)

{

    size[now]=; maxx[now]=;

    for (int i=head[now]; i; i=edge[i].next)

        if (edge[i].to!=last && !visit[edge[i].to])

            {

                DFSRoot(edge[i].to,now);

                size[now]+=size[edge[i].to];

                maxx[now]=max(maxx[now],size[edge[i].to]);

            }

    maxx[now]=max(maxx[now],Sz-size[now]);

    if (maxx[now]<maxx[root]) root=now;

}

void Get(int x,int last,int Dis)

{

    D[++dfn]=Dis; L[dfn]=pl,R[dfn]=pr;

    for (int i=head[x]; i; i=edge[i].next)

        if (!visit[edge[i].to] && edge[i].to!=last)

            Get(edge[i].to,x,Dis+edge[i].val);

}

void Divide(int x)

{

    visit[x]=;

    pl=pr=++dfn;

    for (int i=head[x]; i; i=edge[i].next)

        if (!visit[edge[i].to]) Get(edge[i].to,x,edge[i].val),pr=dfn;

    for (int i=head[x]; i; i=edge[i].next)

        if (!visit[edge[i].to])

            {

                Sz=size[edge[i].to]; root=;

                DFSRoot(edge[i].to,x);

                Divide(root);

            }

}

int log2[MAXM],dp[][MAXM];

int Max(int x,int y) {return D[x]>D[y]? x:y;}

void ST()

{

    log2[]=-;

    for (int i=; i<=N; i++)

        if (i&(i-)) log2[i]=log2[i-]; else log2[i]=log2[i-]+;

    for (int i=; i<=dfn; i++) dp[][i]=i;

    for (int j=; (<<j)<=dfn; j++)

        for (int i=; i+(<<j)-<=dfn; i++)

            dp[j][i]=Max(dp[j-][i],dp[j-][i+(<<j-)]);

}

inline int RMQ(int l,int r)

{

    int tmp=log2[r-l+];

    return Max(dp[tmp][l],dp[tmp][r-(<<tmp)+]);

}

struct HeapNode

{

    int ip,L,R,pos;

    HeapNode (int ip=,int L=,int R=,int pos=)

        : ip(ip),L(L),R(R),pos(pos) {}

    bool operator < (const HeapNode & A) const

        {return D[ip]+D[pos]<D[A.ip]+D[A.pos];}

};

priority_queue<HeapNode>heap;

int main()

{

    N=read(),M=read();

    for (int x,y,z,i=; i<=N-; i++) x=read(),y=read(),z=read(),InsertEdge(x,y,z);

    maxx[root=]=Sz=N;

    DFSRoot(,);

    Divide(root);

    ST();

    for (int i=; i<=dfn; i++)

        heap.push( HeapNode(i,L[i],R[i],RMQ(L[i],R[i])) );

    while (M--)

        {

            HeapNode now=heap.top(); heap.pop();

            printf("%d\n",D[now.ip]+D[now.pos]);

            HeapNode ls=now; ls.R=now.pos-;

            if (ls.R>=ls.L) ls.pos=RMQ(ls.L,ls.R),heap.push(ls);

            HeapNode rs=now; rs.L=now.pos+;

            if (rs.R>=rs.L) rs.pos=RMQ(rs.L,rs.R),heap.push(rs);

        }

    return ;

}

一天前刚写超级钢琴，写起来就非常顺畅了

相关文章