1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define MAXN 1000001 5  6 using namespace std; 7  8 int n, m, cnt, ans; 9 int head[MAXN], to[MAXN], next[MAXN], deep[MAXN], f[MAXN][21];10 11 inline void add(int x, int y)12 {13     to[cnt] = y;14     next[cnt] = head[x];15     head[x] = cnt++;16 }17 18 inline void dfs(int u)19 {20     int i, v;21     deep[u] = deep[f[u][0]] + 1;22     for(i = 0; f[u][i]; i++) f[u][i + 1] = f[f[u][i]][i];23     for(i = head[u]; i != -1; i = next[i])24     {25         v = to[i];26         if(!deep[v]) f[v][0] = u, dfs(v);27     }28 }29 30 inline int lca(int x, int y)31 {32     int i;33     if(deep[x] < deep[y]) swap(x, y);34     for(i = 20; i >= 0; i--)35         if(deep[f[x][i]] >= deep[y])36             x = f[x][i];37     if(x == y) return x;38     for(i = 20; i >= 0; i--)39         if(f[x][i] != f[y][i])40             x = f[x][i], y = f[y][i];41     return f[x][0];42 }43 44 int main()45 {46     int i, x, y, z, a;47     scanf("%d %d", &n, &m);48     memset(head, -1, sizeof(head));49     for(i = 1; i < n; i++)50     {51         scanf("%d %d", &x, &y);52         add(x, y);53         add(y, x);54     }55     deep[1] = 1;56     dfs(1);57     for(i = 1; i <= m; i++)58     {59         scanf("%d %d %d", &x, &y, &z);60         a = lca(x, y) ^ lca(x, z) ^ lca(y, z);61         ans = deep[x] + deep[a] - 2 * deep[lca(x, a)];62         ans += deep[y] + deep[a] - 2 * deep[lca(y, a)];63         ans += deep[z] + deep[a] - 2 * deep[lca(z, a)];64         printf("%d %d\n", a, ans);65     }66     return 0;67 }