首页 > 代码库 > bzoj1787
bzoj1787
lca裸题,画画图看看就可以了,找出那个一次公共祖先,求距离
#include<iostream> #include<set> #include<cstring> #include<algorithm> #include<cmath> #include<cstdio> #include<vector> using namespace std; int n,m,u,v,a,b,c,ans,temp1; int used[1000010],dis[1000010],dep[1000010]; int acs[1000010][23]; vector<int>graph[1000010]; void dfs(int u,int d) { used[u]=1; dep[u]=d; for(int i=0;i<graph[u].size();i++) { int v=graph[u][i]; if(!used[v]) { acs[v][0]=u; dfs(v,d+1); } } } void get_acs() { for(int j=1;j<=22;j++) for(int i=1;i<=n;i++) if(acs[i][j-1]<0) acs[i][j]=-1; else acs[i][j]=acs[acs[i][j-1]][j-1]; } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); int d=dep[x]-dep[y]; for(int k=22;k>=0;k--) if(acs[x][k]!=-1&&(d&(1<<k))) x=acs[x][k]; if(x==y) return x; for(int k=22;k>=0;k--) if(acs[x][k]>0&&acs[y][k]>0&&acs[x][k]!=acs[y][k]) { x=acs[x][k]; y=acs[y][k]; } return acs[x][0]; } inline int calc(int x,int y) { int temp=lca(x,y); return abs(dep[x]-dep[temp])+abs(dep[y]-dep[temp]); } int main() { cin>>n>>m; for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); graph[u].push_back(v); graph[v].push_back(u); } memset(acs,-1,sizeof(acs)); dfs(1,1); get_acs(); // cout<<endl; for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); int x=lca(a,b); int y=lca(b,c); int z=lca(c,a); if(x==y) temp1=z; else if(y==z) temp1=x; else if(x==z) temp1=y; ans=calc(a,temp1)+calc(b,temp1)+calc(c,temp1); printf("%d %d\n",temp1,ans); } return 0; }
bzoj1787
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。