Title:

1832: [AHOI2008] Party

Analysis:

Sometimes it's cool to do water problems.
Find out the LCA first between two, and find that at least two LCAs are the same. This repetitive LCA is also the shallowest one. Then we choose the non-repetitive LCA, because if we choose this repetitive LCA, the repetitive LCA will go to another LCA twice, and vice versa, only once.
The distance between three points is
\(dis[x] + dis[y] + dis[z] - dis[LCA(x, y)]- dis[LCA(x, z)]- dis[LCA(y, z)]\)

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, num;
int head[N], dep[N], f[N], size[N], top[N], son[N];
struct node {
    int v, nx;
} e[N];

template<class T>inline void read(T &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x;
    return ;
}

inline void add(int u, int v) {
    e[++num].nx = head[u], e[num].v = v, head[u] = num;
}

void dfs1(int u, int fa) {
    size[u] = 1;
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (v != fa) {
            dep[v] = dep[u] + 1;
            f[v] = u;
            dfs1(v, u);
            size[u] += size[v];
            if (size[v] > size[son[u]]) son[u] = v;
        }
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    if (son[u]) dfs2(son[u], t);
    for (int i = head[u]; ~i; i = e[i].nx) {
        int v = e[i].v;
        if (v != f[u] && v != son[u]) dfs2(v, v);
    }
}

int lca(int x, int y) {
    int fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);
        x = f[fx], fx = top[x];
    }
    return dep[x] < dep[y] ? x : y;
}

int main() {
    memset(head, -1, sizeof(head));
    read(n), read(m);
    for (int i = 1, x, y; i < n; ++i) read(x), read(y), add(x, y), add(y, x);
    f[1] = 0, dep[1] = 1;
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1, x, y, z; i <= m; ++i) {
        read(x), read(y), read(z);
        int a = lca(x, y), b = lca(x, z), c = lca(y, z);
        int tmp = (dep[a] == dep[b]) ? c : ((dep[a] == dep[c]) ? b : a);
        printf("%d %d\n", tmp, dep[x] + dep[y] + dep[z] - dep[a] - dep[b] - dep[c]);
    }
}