欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bzoj3784: 树上的路径【点分治+ST表+优先队列】

程序员文章站 2022-05-08 18:29:08
...

Description

给定一个N个结点的树,结点用正整数1..N编号。每条边有一个正整数权值。用d(a,b)表示从结点a到结点b路边上经过边的权值。其中要求a

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 )

解题思路:

我们先思考如果不是树是序列该怎么做。
由于权值都大于0,所以最优的点对肯定是形如(1,i)的点对,那么将这样的n个点对都放入堆中。
每次从堆中取一个(l,r),然后把(l+1,r)再丢进去(当然要求丢进去的点对合法)。

再考虑树上,有没有一种树的序列可以像上面一样呢?那就是点分治序。
考虑这道题点剖以后,得到一个长度为nlogn的点分治序列,那每个点i可以选的另一个点j肯定满足:
2、i与j是同一个分治中心。
3、i与j不属于分治中心的同一颗子树内。
设D[i]表示序列中第i个点到它分治中心的距离。
序列中每个点维护一个四元组(id,l,r,p)表示第id个点可以和序列区间(l,r)中的点组成点对,其中最优匹配点为p。
也放入堆中,按D[id]+D[p]排序。
每取出一个四元组,就把(id,l,p-1,query(l,p-1)),(id,p+1,r,query(p+1,r))放入堆中,其中query(l,r)表示区间(l,r)中D的最大值,可以用ST表实现。
重复m次即为答案。

#include<bits/stdc++.h>
using namespace std;

int getint()
{
    int i=0,f=1;char c;
    for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
    if(c=='-')f=-1,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}

const int N=50005;
int n,m,cnt,root,totsize,st,ed;
int tot,first[N],nxt[N<<1],to[N<<1],w[N<<1];
int D[20*N],L[20*N],R[20*N],dis[N],size[N],maxsub[N];
int Log[20*N],mx[20][20*N];
bool vis[N];
struct node{int id,l,r,p;};
inline bool operator < (const node &a,const node &b)
{return D[a.id]+D[a.p]<D[b.id]+D[b.p];}
priority_queue<node>q;

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

void add(int x,int y,int z)
{
    nxt[++tot]=first[x],first[x]=tot,to[tot]=y,w[tot]=z;
}

void findG(int u,int fa)
{
    size[u]=1;maxsub[u]=0;
    for(int e=first[u];e;e=nxt[e])
    {
        int v=to[e];
        if(v==fa||vis[v])continue;
        findG(v,u);size[u]+=size[v];
        maxsub[u]=max(maxsub[u],size[v]);
    }
    maxsub[u]=max(maxsub[u],totsize-size[u]);
    if(maxsub[u]<maxsub[root])root=u;
}

void dfs(int u,int fa)
{
    D[++cnt]=dis[u],L[cnt]=st,R[cnt]=ed;
    for(int e=first[u];e;e=nxt[e])
    {
        int v=to[e];
        if(v==fa||vis[v])continue;
        dis[v]=dis[u]+w[e];
        dfs(v,u);
    }
}

void solve(int u)
{
    vis[u]=1;D[st=++cnt]=dis[u]=0;
    for(int e=first[u];e;e=nxt[e])
    {
        int v=to[e];
        if(vis[v])continue;
        ed=cnt;dis[v]=dis[u]+w[e];
        dfs(v,u);
    }
    for(int e=first[u];e;e=nxt[e])
    {
        int v=to[e];
        if(vis[v])continue;
        root=0,maxsub[0]=totsize=size[v];
        findG(v,u),solve(root);
    }
}

int query(int l,int r)
{
    int t=Log[r-l+1];
    return Max(mx[t][l],mx[t][r-(1<<t)+1]);
}

void ST_init()
{
    for(int i=2;i<=cnt;i++)Log[i]=Log[i>>1]+1;
    for(int i=1;i<=cnt;i++)mx[0][i]=i;
    for(int j=1;j<20;j++)
        for(int i=1;i<=cnt;i++)
            if(i+(1<<j)-1<=cnt)
                mx[j][i]=Max(mx[j-1][i],mx[j-1][i+(1<<j-1)]);
}

int main()
{
    //freopen("lx.in","r",stdin);
    //freopen("lx.out","w",stdout);
    n=getint(),m=getint();
    for(int i=1;i<n;i++)
    {
        int x=getint(),y=getint(),z=getint();
        add(x,y,z),add(y,x,z);
    }
    root=0,maxsub[0]=totsize=n;
    findG(1,0);solve(root);
    ST_init();
    for(int i=1;i<=cnt;i++)if(L[i])
        q.push((node){i,L[i],R[i],query(L[i],R[i])});
    while(m--)
    {
        node t=q.top();q.pop();
        printf("%d\n",D[t.id]+D[t.p]);
        if(t.l<=t.p-1)q.push((node){t.id,t.l,t.p-1,query(t.l,t.p-1)});
        if(t.p+1<=t.r)q.push((node){t.id,t.p+1,t.r,query(t.p+1,t.r)});
    }
    return 0;
}