【BZOJ】3784: 樹上的路徑-點分治序+ST表

傳送門:bzoj3784

題解

前 k k k大比較好做(之前看成前 k k k小了)

所有的最優前k步問題最終都轉成了bzoj2006: [NOI2010]超級鋼琴…

如何将序列上問題轉到樹上，并維護本質不同的拓展呢？

考慮點分治，把樹上問題轉回點分治序上的問題：

對于序列中的每個點 i i i，權值 v i = d i s ( v i , i 的 分 治 重 心 ) v_i=dis(v_i,i的分治重心) vi​=dis(vi​,i的分治重心)，對于 i i i可與其組合的點 j j j滿足：

1. 屬于同一個分治重心

2. i , j i,j i,j不在分治重心的某個子結點的同一子樹内

   這樣的 j j j就是在點分治序上是連續的兩段，由于 ( i , j ) , ( j , i ) (i,j),(j,i) (i,j),(j,i)等價，是以固定某個方向的一段即可。

在優先隊列中維護這樣的四元組 ( u , l , r , p ) (u,l,r,p) (u,l,r,p)表示點 u u u可選範圍為 [ l , r ] [l,r] [l,r]且其中值最大的為 v p v_p vp​，按 v i + v p v_i+v_p vi​+vp​降序排序。

拓展 ( u , l , r , p ) → ( u , l , p − 1 , m a x ( l , p − 1 ) ) , ( u , p + 1 , r , m a x ( p + 1 , r ) ) (u,l,r,p)\to (u,l,p-1,max(l,p-1)),(u,p+1,r,max(p+1,r)) (u,l,r,p)→(u,l,p−1,max(l,p−1)),(u,p+1,r,max(p+1,r))

S T ST ST表維護區間最大值。

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=50010,M=1e6+10;

int n,m,d[M],mx[20][M],bel[M],brt[M],lg[M];
int head[N],to[N<<1],nxt[N<<1],w[N<<1],tot;
int df[N],ot[N],sz[N],dfn,S,MN,rt,nw;
bool vs[N];

inline int ask(int l,int r)
{
	int bs=lg[r-l+1],x=mx[bs][l],y=mx[bs][r-(1<<bs)+1];
	return d[x]>d[y]?x:y;
}

struct P{
    int u,l,r,p,v;
    P(){};
    P(int u_,int l_,int r_){u=u_;l=l_;r=r_;p=ask(l,r);v=d[u]+d[p];};
    bool operator <(const P&ky)const{return v<ky.v;}
}dg;
priority_queue<P>que;

inline void lk(int u,int v,int vv)
{to[++tot]=v;nxt[tot]=head[u];head[u]=tot;w[tot]=vv;}

void fdrt(int x,int fr)
{
	int i,j,mxx=0;sz[x]=1;
	for(i=head[x];i;i=nxt[i]){
		j=to[i];if(j==fr || vs[j]) continue;
		fdrt(j,x);sz[x]+=sz[j];
		mxx=max(mxx,sz[j]);
	}
	mxx=max(mxx,S-sz[x]);
	if(mxx<MN) MN=mxx,rt=x;
}

void dfs(int x,int fr,int dis)
{
	int i,j;
	d[(df[x]=++dfn)]=dis;
	brt[dfn]=nw;mx[0][dfn]=dfn;
	for(i=head[x];i;i=nxt[i]){
		j=to[i];if(j==fr || vs[j]) continue;
		dfs(j,x,dis+w[i]);
	}
	ot[df[x]]=dfn;
}

void col(int x,int fr)
{
	int i,j;bel[df[x]]=nw;
	for(i=head[x];i;i=nxt[i]){
		j=to[i];if(j==fr || vs[j]) continue;
		col(j,x);
	}
}

void divide(int x)
{
	int i,j,sum=S;vs[x]=true;
	nw=dfn+1;dfs(x,0,0);
	for(i=head[x];i;i=nxt[i]){
		j=to[i];if(vs[j]) continue;
		nw=df[j];col(j,x);
	}
	for(i=head[x];i;i=nxt[i]){
		j=to[i];if(vs[j]) continue;
		S=sz[j]<sz[x]?sz[j]:sum-sz[x];MN=N;
		fdrt(j,x);divide(rt);
	}
}

int main(){
	int i,j,x,y,z;
	scanf("%d%d",&n,&m);
	for(i=1;i<n;++i){scanf("%d%d%d",&x,&y,&z);lk(x,y,z);lk(y,x,z);}
	S=n;MN=N;fdrt(1,0);divide(rt);
	for(i=2;i<=dfn;++i) lg[i]=lg[i>>1]+1;
	for(j=1;(1<<j)<=dfn;++j)
		for(i=1;i+(1<<j)-1<=dfn;++i){
			x=mx[j-1][i];y=mx[j-1][i+(1<<(j-1))];
			mx[j][i]= d[x]>d[y]?x:y;
		}
	for(i=1;i<=dfn;++i) if(bel[i]){
		if(brt[i]<bel[i]) que.push(P(i,brt[i],bel[i]-1));
//		if(ot[brt[i]]>ot[bel[i]]) que.push(P(i,ot[bel[i]]+1,ot[brt[i]]));
	}
	for(;m;--m){
		dg=que.top();que.pop();printf("%d\n",dg.v);
		if(dg.l<dg.p) que.push(P(dg.u,dg.l,dg.p-1));
		if(dg.r>dg.p) que.push(P(dg.u,dg.p+1,dg.r));
	}
	return 0;
}