记录编号	581391	评测结果	AAAAAAAAAA
题目名称	[AHOI2008]聚会	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	3.477 s
提交时间	2023-08-02 14:58:30	内存使用	33.19 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 500010,M = 1000010;
int n,t,Q,ans;
struct made{
    int ver,nx;
}e[M];
int hd[N],tot,d[N],f[N][20];
void add_(int x,int y){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],hd[x] = tot;
    return;
}
void init(){
    scanf("%d%d",&n,&Q);
    t = int(log(n)/log(2))+1;//log2(n);
    for(int i = 1;i < n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add_(x,y);add_(y,x);
    }
    return;
}
void bfs(){
    queue<int>q;
    d[1] = 1;
    q.push(1);
    while(!q.empty()){
        int x = q.front();q.pop();
        for(int i = hd[x];i;i = e[i].nx){
            int y = e[i].ver;
            if(d[y])continue;
            d[y] = d[x] + 1;
            f[y][0] = x;
            for(int j = 1;j <= t;j++){
                f[y][j] = f[f[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
    return;
}//bfs扫描一遍 
int LCA(int x,int y){
    if(d[x] > d[y])swap(x,y);
    for(int i = t;i >= 0;i--){
        if(d[f[y][i]] >= d[x])y = f[y][i];
    }
    if(x == y)return x;
    for(int i = t;i >= 0;i--){
        if(f[x][i] != f[y][i])x = f[x][i],y = f[y][i];
    }
    return f[x][0];
}//正常LCA 
int su_(int x,int y,int z){
    int s = LCA(x,y);
    return d[x]+d[y]-2*d[s]+d[s]+d[z]-2*d[LCA(s,z)];
}
void work(){//!!!!!!!!!!!!!!!!!!!!!
    for(int i = 1;i <= Q;i++){
        ans = INT_MAX;
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        int s1 = LCA(x,y),s2 = LCA(x,z),s3 = LCA(y,z);
        if(s1 == s2)printf("%d ",s3);
        else if(s1 == s3)printf("%d ",s2);
        else if(s2 == s3)printf("%d ",s1);//选城市
        s1 = su_(x,y,z),s2 = su_(x,z,y),s3 = su_(z,y,x);//x,y,z之间距离 
        ans = min(s1,min(s2,min(s3,ans)));//最小的 
        printf("%d\n",ans);
    }
    return;
}//!!!!!!!!!!!!!!!!!!!!!!
int main(){
    freopen("AHOI2008party.in","r",stdin);
    freopen("AHOI2008party.out","w",stdout);
    init();
    bfs();
    work();
    
    return 0;
    
}