[bzoj1787][Ahoi2008]紧急集合

时间:2024-07-08 21:37:56

Description

给定一棵大小为[bzoj1787][Ahoi2008]紧急集合的树,有[bzoj1787][Ahoi2008]紧急集合组询问,每组询问给三个点[bzoj1787][Ahoi2008]紧急集合,求到这三个点距离和最小的点及最小距离和.

Input

第一行两个数[bzoj1787][Ahoi2008]紧急集合.

接下来[bzoj1787][Ahoi2008]紧急集合行,每行两个数[bzoj1787][Ahoi2008]紧急集合表示[bzoj1787][Ahoi2008]紧急集合[bzoj1787][Ahoi2008]紧急集合有一条边.

最后[bzoj1787][Ahoi2008]紧急集合行,每行[bzoj1787][Ahoi2008]紧急集合个数[bzoj1787][Ahoi2008]紧急集合,为一组询问.

Output

一共[bzoj1787][Ahoi2008]紧急集合行,每行两个数,表示到三个点距离和最小的点及最小距离和.

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

[bzoj1787][Ahoi2008]紧急集合

Solution

[bzoj1787][Ahoi2008]紧急集合个点两两求[bzoj1787][Ahoi2008]紧急集合,只会有[bzoj1787][Ahoi2008]紧急集合种情况:

1.[bzoj1787][Ahoi2008]紧急集合均相同;

2.有[bzoj1787][Ahoi2008]紧急集合[bzoj1787][Ahoi2008]紧急集合与其他不同.

如果均相同,[bzoj1787][Ahoi2008]紧急集合为答案,否则为与其他不同的那个[bzoj1787][Ahoi2008]紧急集合.

(画图简单推推即可理解)

距离可用深度[bzoj1787][Ahoi2008]紧急集合求出.

#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;
}