首页 > 代码库 > bzoj1787 [Ahoi2008]Meet 紧急集合

bzoj1787 [Ahoi2008]Meet 紧急集合

2024-08-03 21:45:05   219人阅读

Description

Input

Output

Sample Input

6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

Sample Output


5 2
2 5
4 1
6 0

HINT

社会实践完滚回来想刷水结果被水题虐了

先算出两两的lca，一定有两个lca是一样的

假设对于询问(x,y,z),xy的lca是a，xz的lca是b，yz的lca是c，不妨设xyz不在链上，并且长成这样：

 

那么一定有lca(a,z)=c，即lca(x,z)=c且lca(y,z)=c

在同一链上更简单了

然后只要把剩下的那个不同的lca当做集合的地点就好了，这个也很容易理解，自己画画图就好了

QAQ因为数组开小而连跪3次……不要学我啊

#include<cstdio>#include<iostream>using namespace std;#define LL long long#define N 1000010inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}struct edge{	int to,next;}e[2*N];int head[N];int depth[N];int go[N][25];bool mrk[N];int n,m,cnt,x,y,z,xy,xz,yz,sum;inline int abs(int a){return a<0?-a:a;}inline void ins(int u,int v){	e[++cnt].to=v;	e[cnt].next=head[u];	head[u]=cnt;}inline void insert(int u,int v){	ins(u,v);	ins(v,u);}inline void dfs(int x,int dep){	if (mrk[x])return;	mrk[x]=1;depth[x]=dep;	for (int i=1;i<=20;i++) go[x][i]=go[go[x][i-1]][i-1];	for (int i=head[x];i;i=e[i].next)	  if (!mrk[e[i].to])	  {	  	go[e[i].to][0]=x;	  	dfs(e[i].to,dep+1);	  }} inline int lca(int x,int y){	if (depth[x]<depth[y])swap(x,y);	int res=depth[x]-depth[y];	for(int i=0;i<=19;i++)	  if (res & (1<<i)) x=go[x][i];	for (int i=19;i>=0;i--)	  if (go[x][i]!=go[y][i])	  {	  	x=go[x][i];	  	y=go[y][i];	  }	if (x==y)return x;	return go[x][0];}inline int dis(int a,int b){	int t=lca(a,b);	return depth[a]+depth[b]-2*depth[t];}inline int calc(){	xy=lca(x,y); xz=lca(x,z); yz=lca(y,z);	int t;	if (xy==xz)t=yz;	if (xy==yz)t=xz;	if (xz==yz)t=xy;	int ans=dis(x,t)+dis(y,t)+dis(z,t);	printf("%d %d\n",t,ans);}int main(){	n=read();m=read();	for (int i=1;i<n;i++)	{		int s=read(),t=read();		insert(s,t);	}	for(int i=0;i<20;i++)go[n/2][i]=n/2;	dfs(n/2,1);	for(int i=1;i<=m;i++)	{		x=read();		y=read();		z=read();		calc();	}}

 

bzoj1787 [Ahoi2008]Meet 紧急集合


联系
我们