首页 > 代码库 > 【bzoj1787】[Ahoi2008]Meet 紧急集合
【bzoj1787】[Ahoi2008]Meet 紧急集合
1787: [Ahoi2008]Meet 紧急集合
Time Limit: 20 Sec Memory Limit: 162 MBSubmit: 2466 Solved: 1117
[Submit][Status][Discuss]
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
2 5
4 1
6 0
【题解】
记住一个结论:三个点的最小距离点等于两两的lca中与其他两个lca不同的lca
然后就很水了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<ctime> 6 #include<cmath> 7 #include<algorithm> 8 using namespace std; 9 #define MAXN 500010 10 struct node{int y,next;}e[MAXN*2]; 11 int n,m,len,ans,Link[MAXN],f[MAXN],deep[MAXN],anc[MAXN][25]; 12 inline int read() 13 { 14 int x=0,f=1; char ch=getchar(); 15 while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();} 16 while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();} 17 return x*f; 18 } 19 void insert(int x,int y) {e[++len].next=Link[x];Link[x]=len;e[len].y=y;} 20 void dfs(int x,int fa) 21 { 22 anc[x][0]=f[x]; 23 for(int i=1;i<=20;i++) anc[x][i]=anc[anc[x][i-1]][i-1]; 24 for(int i=Link[x];i;i=e[i].next) 25 if(e[i].y!=fa) 26 { 27 deep[e[i].y]=deep[x]+1; 28 f[e[i].y]=x; 29 dfs(e[i].y,x); 30 } 31 } 32 int lca(int x,int y) 33 { 34 if(deep[x]<deep[y]) swap(x,y); 35 for(int i=20;i>=0;i--) if(deep[anc[x][i]]>=deep[y]) x=anc[x][i]; 36 if(x==y) return x; 37 for(int i=20;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i]; 38 return f[x]; 39 } 40 int cal(int a,int b,int c) {if(a==b)return c;else if(a==c)return b;else return a;} 41 int dis(int x,int y) {int t=lca(x,y);return deep[x]+deep[y]-2*deep[t];} 42 int main() 43 { 44 //freopen("cin.in","r",stdin); 45 //freopen("cout.out","w",stdout); 46 n=read(); m=read(); 47 for(int i=1;i<n;i++) {int x=read(),y=read(); insert(x,y); insert(y,x);} 48 deep[1]=1; dfs(1,0); 49 for(int i=1;i<=m;i++) 50 { 51 int x=read(),y=read(),z=read(); 52 int a=lca(x,y),b=lca(x,z),c=lca(y,z); 53 int p=cal(a,b,c); 54 ans=dis(x,p)+dis(y,p)+dis(z,p); 55 printf("%d %d\n",p,ans); 56 } 57 return 0; 58 }
【bzoj1787】[Ahoi2008]Meet 紧急集合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。