首页 > 代码库 > [bzoj1787][Ahoi2008]紧急集合
[bzoj1787][Ahoi2008]紧急集合
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
Solution
对个点两两求,只会有种情况:
1.均相同;
2.有个与其他不同.
如果均相同,为答案,否则为与其他不同的那个.
(画图简单推推即可理解)
距离可用深度求出.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define K 20 #define N 500005 using namespace std; struct graph{ int nxt,to; }e[N<<1]; int f[N][K],g[N],dep[N],a,b,c,n,m,x,y,z,cnt; stack<int> s; inline int read(){ int ret=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ ret=(ret<<1)+(ret<<3)+c-‘0‘; c=getchar(); } return ret; } inline void addedge(int x,int y){ e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y; } inline void dfs(int u){ dep[u]=1;s.push(u); while(!s.empty()){ u=s.top();s.pop(); if(u==1) for(int i=0;i<K;++i) f[u][i]=1; else for(int i=1;i<K;++i) f[u][i]=f[f[u][i-1]][i-1]; for(int i=g[u];i;i=e[i].nxt) if(!dep[e[i].to]){ dep[e[i].to]=dep[u]+1; f[e[i].to][0]=u; s.push(e[i].to); } } } inline int swim(int x,int h){ for(int i=0;h;++i,h>>=1) if(h&1) x=f[x][i]; return x; } inline int lca(int x,int y){ if(dep[x]<dep[y]){ int t=x;x=y;y=t; } x=swim(x,dep[x]-dep[y]); if(x==y) return x; int i; while(true){ for(i=0;f[x][i]!=f[y][i];++i); if(!i) return f[x][0]; x=f[x][i-1];y=f[y][i-1]; } } inline void init(){ n=read();m=read(); for(int i=1,j,k;i<n;++i){ j=read();k=read(); addedge(j,k);addedge(k,j); } dfs(1); while(m--){ x=read();y=read();z=read(); a=lca(x,y);b=lca(y,z);c=lca(x,z); if(a==b&&b==c) printf("%d %d\n",a,dep[x]+dep[y]+dep[z]-dep[a]*3); else if(a==b) printf("%d %d\n",c,dep[x]+dep[y]+dep[z]-dep[c]-(dep[a]<<1)); else if(a==c) printf("%d %d\n",b,dep[x]+dep[y]+dep[z]-dep[b]-(dep[a]<<1)); else printf("%d %d\n",a,dep[x]+dep[y]+dep[z]-dep[a]-(dep[b]<<1)); } } int main(){ freopen("meet.in","r",stdin); freopen("meet.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }
[bzoj1787][Ahoi2008]紧急集合
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。