首页 > 代码库 > bzoj1787 [Ahoi2008]Meet 紧急集合
bzoj1787 [Ahoi2008]Meet 紧急集合
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
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 紧急集合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。