首页 > 代码库 > 【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 Input
5 2
2 5
4 1
6 0
2 5
4 1
6 0
HINT
【解析】
三个点两两的lca一共有3个,其中两个一样的,那个不一样的就是集合点。
为什么是那个点呢???求助~
然后求三个点到集合点的距离。
【代码】
#include<iostream> #include<cstdio> using namespace std; #define N 500003 int sumedge,n,m,x,y,A,B,C,D,a,b,c,d,L; int head[N],size[N],deep[N],dis[N],dad[N],top[N]; struct Edge { int x,y,next; Edge(int x=0,int y=0,int next=0):x(x),y(y),next(next){} }edge[N<<1]; inline int read()//读入优化 { int 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; } inline void add_edge(int x,int y)//加边 { edge[++sumedge]=Edge(x,y,head[x]); head[x]=sumedge; } inline void dfs(int x)//树剖求lca { size[x]=1; deep[x]=deep[dad[x]]+1; for(int i=head[x];i;i=edge[i].next) { if(dad[x]!=edge[i].y) { dad[edge[i].y]=x; dis[edge[i].y]=dis[x]+1; dfs(edge[i].y); size[x]+=size[edge[i].y]; } } } inline void dfs1(int x)//树剖求lca { int s=0; if(!top[x])top[x]=x; for(int i=head[x];i;i=edge[i].next) { if(dad[x]!=edge[i].y&&size[edge[i].y]>size[s]) { s=edge[i].y; } } if(s) { top[s]=top[x]; dfs1(s); } for(int i=head[x];i;i=edge[i].next) { if(dad[x]!=edge[i].y&&edge[i].y!=s) dfs1(edge[i].y); } } inline int lca(int x,int y)//树剖求Lca { for(;top[x]!=top[y];) { if(deep[top[x]]>deep[top[y]]) swap(x,y); y=dad[top[y]]; } if(deep[x]>deep[y]) swap(x,y); return x; } inline int l(int x,int y)//树上两点之间的最短路径 两个点到跟的路径长度减去两倍的lca到根的长度。 { return dis[x]+dis[y]-2*dis[lca(x,y)]; } int main() { n=read();m=read();//n个点 m个询问 for(int i=1;i<n;i++) { x=read();y=read(); add_edge(x,y);//加边 add_edge(y,x); } dfs(1);//树剖求lca的dfs dfs1(1); for(int i=1;i<=m;i++) { a=read();b=read();c=read(); A=lca(a,b);B=lca(a,c);C=lca(b,c); D=A^B^C;//三个lca中有两个相同的 D是那个不同的 L=l(a,D)+l(b,D)+l(c,D);//三点到D的距离 用树上两点之间的最短路径做。 printf("%d %d\n",D,L); } return 0; }
//不知道为什么同学用的树剖和vector数组存边一直re。。。。然后写上读入优化就过了???还好我用的邻接表~
【bzoj1787】[Ahoi2008]Meet 紧急集合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。