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

BZOJ3784:树上的路径

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

浅谈树分治:https://www.cnblogs.com/AKMer/p/10014803.html

题目传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=3784

难得地看了题解,发现居然还有点分序这么个玩意儿……

对于点分治时遍历过的点的长度为\(nlogn\)的序列,我们称它为点分序。

然后这题就是树上超级钢琴,在点分序上做就行了。对于每一条边,在点分序里能与其匹配的边是一段区间。

时间复杂度:\(O(nlogn*(1+log(nlogn)))\)

空间复杂度:\(O(nlogn*log(nlogn))\)

代码如下:

#include <cstdio>
#include <algorithm>
using namespace std;
 
const int maxn=5e4+5;
 
bool vis[maxn];
int n,m,mx,rt,N,tot,cnt,L,R;
int now[maxn],pre[maxn*2],son[maxn*2],val[maxn*2];
int siz[maxn],a[maxn*20],Log[maxn*20],f[20][maxn*20];
 
int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}
 
void add(int a,int b,int c) {
    pre[++tot]=now[a];
    now[a]=tot,son[tot]=b,val[tot]=c;
}
 
struct node {
    int v,pos,l,r;
 
    node() {}
 
    node(int _v,int _pos,int _l,int _r) {
        v=_v,pos=_pos,l=_l,r=_r;
    }
 
    bool operator<(const node &a)const {
        return v<a.v;
    }
};
 
struct Heap {
    int tot;
    node tree[maxn*26];
 
    void ins(node res) {
        tree[++tot]=res;
        int pos=tot;
        while(pos>1) {
            if(tree[pos>>1]<tree[pos])
                swap(tree[pos>>1],tree[pos]),pos>>=1;
            else break;
        }
    }
 
    node pop() {
        node res=tree[1];
        tree[1]=tree[tot--];
        int pos=1,son=2;
        while(son<=tot) {
            if(son<tot&&tree[son]<tree[son|1])son|=1;
            if(tree[pos]<tree[son])
                swap(tree[son],tree[pos]),pos=son,son=pos<<1;
            else break;
        }
        return res;
    }
}T;
 
void find_rt(int fa,int u) {
    int res=0;siz[u]=1;
    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
        if(!vis[v]&&v!=fa)find_rt(u,v),siz[u]+=siz[v],res=max(res,siz[v]);
    res=max(res,N-siz[u]);
    if(res<mx)mx=res,rt=u;
}
 
void solve(int fa,int u,int dis) {
    a[++cnt]=dis;T.ins(node(a[mx]+dis,cnt,L,R)),siz[u]=1;
    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
        if(!vis[v]&&v!=fa)solve(u,v,dis+val[p]),siz[u]+=siz[v];
}
 
void work(int u,int size) {
    N=size,mx=rt=n+1,find_rt(0,u);
    u=rt,vis[u]=1,a[++cnt]=0,L=cnt,mx=cnt;
    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
        if(!vis[v]) {
            R=cnt,solve(u,v,val[p]);
            for(int j=R+1;j<=cnt;j++)
                if(a[j]>a[mx])mx=j;
        }
    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])
        if(!vis[v])work(v,siz[v]);
}
 
int fake(int num1,int num2) {
    if(a[num1]>a[num2])return num1;
    return num2;
}
 
int query(int l,int r) {
    int x=Log[r-l+1];
    return fake(f[x][l],f[x][r-(1<<x)+1]);
}
 
void make_st() {
    Log[0]=-1;
    for(int i=1;i<=cnt;i++)
        f[0][i]=i,Log[i]=Log[i>>1]+1;
    for(int i=1;i<=19;i++)
        for(int j=1;j+(1<<i)-1<=cnt;j++)
            f[i][j]=fake(f[i-1][j],f[i-1][j+(1<<(i-1))]);
}
 
int main() {
    n=read(),m=read();
    for(int i=1;i<n;i++) {
        int a=read(),b=read(),c=read();
        add(a,b,c),add(b,a,c);
    }work(1,n),make_st();
    for(int i=1;i<=m;i++) {
        node tmp=T.pop();
        int pos=query(tmp.l,tmp.r);
        if(pos-1>=tmp.l)
            T.ins(node(a[query(tmp.l,pos-1)]+a[tmp.pos],tmp.pos,tmp.l,pos-1));
        if(pos+1<=tmp.r)
            T.ins(node(a[query(pos+1,tmp.r)]+a[tmp.pos],tmp.pos,pos+1,tmp.r));
        printf("%d\n",tmp.v);
    }
    return 0;
}