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

BZOJ3784 : 树上的路径

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

树的点分治,在分治的时候将所有点到根的距离依次放入一个数组q中。

对于一棵子树里的点,合法的路径一定是q[L]..q[R]的某个数加上自己到重心的距离。

定义五元组(v,l,m,r,w),表示当前路径长度为v,在[l,r]里选出最大值m,并加上w。

用大根堆维护这些五元组,每次取出v最大的元素,并扩展出[l,m-1]以及[m+1,r]两个状态,用线段树查询区间最大值。

时间复杂度$O(n\log^2n+m\log n)$。

 

#include<cstdio>
#include<queue>
using namespace std;
const int N=50010,M=800000;
int n,m,i,x,y,z,g[N],v[N<<1],w[N<<1],ok[N<<1],nxt[N<<1],ed;
int all,f[N],son[N],now;
int L,R,q[M],cnt,val[2100000],cp;
struct P{
  int v,l,m,r,w;
  P(){}
  P(int _v,int _l,int _m,int _r=0,int _w=0){v=_v,l=_l,m=_m,r=_r,w=_w;}
  inline bool operator<(const P&b)const{return v<b.v;}
}tmp,pre[M];
priority_queue<P>Q;
inline int merge(int x,int y){return q[x]>q[y]?x:y;}
void build(int x,int a,int b){
  if(a==b){val[x]=a;return;}
  int mid=(a+b)>>1;
  build(x<<1,a,mid),build(x<<1|1,mid+1,b);
  val[x]=merge(val[x<<1],val[x<<1|1]);
}
int ask(int x,int a,int b,int c,int d){
  if(c<=a&&b<=d)return val[x];
  int mid=(a+b)>>1;
  if(d<=mid)return ask(x<<1,a,mid,c,d);
  if(c>mid)return ask(x<<1|1,mid+1,b,c,d);
  return merge(ask(x<<1,a,mid,c,d),ask(x<<1|1,mid+1,b,c,d));
}
inline void extend(int l,int r,int w){
  if(l>r)return;
  int x=ask(1,1,cnt,l,r);
  Q.push(P(q[x]+w,l,x,r,w));
}
inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;ok[ed]=1;nxt[ed]=g[x];g[x]=ed;}
void findroot(int x,int y){
  son[x]=1,f[x]=0;
  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y){
    findroot(v[i],x);
    son[x]+=son[v[i]];
    if(son[v[i]]>f[x])f[x]=son[v[i]];
  }
  if(all-son[x]>f[x])f[x]=all-son[x];
  if(f[x]<f[now])now=x;
}
void dfs(int x,int y,int dis){
  q[++cnt]=dis;
  pre[cp++]=P(L,R,dis);
  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y)dfs(v[i],x,dis+w[i]);
}
void solve(int x){
  int i;L=cnt+1;
  for(i=g[x];i;i=nxt[i])if(ok[i])R=cnt,dfs(v[i],x,w[i]);
  pre[cp++]=P(L,cnt,0);
  for(i=g[x];i;i=nxt[i])if(ok[i]){
    ok[i^1]=0;
    f[0]=all=son[v[i]];
    findroot(v[i],now=0);
    solve(now);
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(ed=i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
  f[0]=all=n;findroot(1,now=0);solve(now);
  build(1,1,cnt);
  for(i=0;i<cp;i++)extend(pre[i].v,pre[i].l,pre[i].m);
  while(m--){
    tmp=Q.top(),Q.pop(),printf("%d\n",tmp.v);
    extend(tmp.l,tmp.m-1,tmp.w);
    extend(tmp.m+1,tmp.r,tmp.w);
  }
  return 0;
}