首页 > 代码库 > 【BZOJ3784】树上的路径 点分治序+ST表

【BZOJ3784】树上的路径 点分治序+ST表

2024-10-10 21:36:03   226人阅读

【BZOJ3784】树上的路径

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 )

题解：“总有那么一种序列，可以满足你某道题的所需的一切性质~”

没错，听说过DFS序吗，听说过BFS序吗，如果你都听说过，那么你听说过点分治序吗？

没错，点分治序，顾名思义，就是点分治时扫过的序列（包括每次找到的重心和从重心出发依次DFS过的所有子树），它的长度是nlogn的。那么这样一个序列有什么性质呢？

如果我们已经确定了一个分治中心和它的子树中的一条链，我们想找到这个分治中心的另一条链（亦或是这个分治中心本身）和它来组成一条路径，那么这些路径的端点在什么位置呢？没错，他们在点分治序上正好是一段连续的序列！并且根据点分治的原理，通过这样我们可以找到树上所有的路径。

那么问题就变成了：给你一个序列，你每次可以从中选取两个数(a,b)，其中对于每一个b，可以与它搭配的a都在一段给定的区间里。这不就是BZOJ2006超级钢琴吗？直接ST表就好了。

#include <cstdio>#include <cstring>#include <iostream>#include <utility>#include <queue>#define mp(A,B,C,D)	make_pair(make_pair(A,B),make_pair(C,D))using namespace std;const int maxn=50010;typedef pair<int,int> pii;int n,m,cnt,maxx,tot,root,nm;int sm[800010][20],to[maxn<<1],next[maxn<<1],val[maxn<<1],head[maxn],siz[maxn];int lp[800010],rp[800010],v[800010],vis[maxn],Log[800010];priority_queue<pair<pii,pii> > pq;int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}int ms(int a,int b){	return v[a]>v[b]?a:b;}void add(int a,int b,int c){	to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;}void getr(int x,int fa){	siz[x]=1;	int i,mx=0;	for(i=head[x];i!=-1;i=next[i])	{		if(vis[to[i]]||to[i]==fa)	continue;		getr(to[i],x),siz[x]+=siz[to[i]],mx=max(mx,siz[to[i]]);	}	if(maxx>max(mx,tot-siz[x]))	root=x,maxx=max(mx,tot-siz[x]);}void getd(int x,int fa,int dep){	v[++nm]=dep,lp[nm]=lp[nm-1],rp[nm]=rp[nm]?rp[nm]:rp[nm-1];	for(int i=head[x];i!=-1;i=next[i])	{		if(vis[to[i]]||to[i]==fa)	continue;		getd(to[i],x,dep+val[i]);	}}void dfs(int x){	vis[x]=1;	int i;	v[++nm]=0,lp[nm]=nm,rp[nm]=nm-1;	for(i=head[x];i!=-1;i=next[i])	{		if(vis[to[i]])	continue;		rp[nm+1]=nm,getd(to[i],x,val[i]);	}	for(i=head[x];i!=-1;i=next[i])	{		if(vis[to[i]])	continue;		tot=siz[to[i]],maxx=1<<30,getr(to[i],x),dfs(root);	}}int query(int a,int b){	if(a>b)	return 0;	int k=Log[b-a+1];	return ms(sm[a][k],sm[b-(1<<k)+1][k]);}int main(){	n=rd(),m=rd();	int i,j,a,b,c,d,x,y;	memset(head,-1,sizeof(head));	for(i=1;i<n;i++)	a=rd(),b=rd(),c=rd(),add(a,b,c),add(b,a,c);	tot=n,maxx=1<<30,getr(1,0),dfs(root);	for(i=1;i<=nm;i++)	sm[i][0]=i;	for(i=2;i<=nm;i++)	Log[i]=Log[i>>1]+1;	for(j=1;(1<<j)<nm;j++)		for(i=1;i+(1<<j)-1<=nm;i++)			sm[i][j]=ms(sm[i][j-1],sm[i+(1<<j-1)][j-1]);	for(i=1;i<=nm;i++)	{		if(lp[i]>rp[i])	continue;		pq.push(mp(v[i]+v[query(lp[i],rp[i])],i,lp[i],rp[i]));	}	for(i=1;i<=m;i++)	{		pii t1=pq.top().first,t2=pq.top().second;		pq.pop();		printf("%d\n",t1.first),x=t1.second,a=t2.first,b=t2.second,y=query(a,b);		c=query(a,y-1),d=query(y+1,b);		if(c)	pq.push(mp(v[x]+v[c],x,a,y-1));		if(d)	pq.push(mp(v[x]+v[d],x,y+1,b));	}	return 0;}

【BZOJ3784】树上的路径 点分治序+ST表


联系
我们