算法

(LCA) $O(m\log n)$

• 树上找一个点，到三个点 $a, b, c$ 的距离之和最小
• 到 $a,b$ 距离最小的点路径在 $a-d-b$ 上，到 $a,c$ 距离最小的点在路径 $a-d-e-c$ 上，到 $b, c$ 距离最小的点在路径 $b, d, e, c$ 上。所以，到三个点距离之和最小的点是 $d$ 点。
• 三个点两两之间求 $lca$，在更深的那个 $lca$ 的位置上。设更深的 $lca$ 为 $f1$，比较浅的 $lca$ 为 $f2$。
• 到三个点的距离之和为 $dep[a] + dep[b] + dep[c] - 2 * dep[f2] - dep[f1]$。

C++ 代码

// 版本1
#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::swap;

const int MAXN = 500005;

struct Node {
    int v;
    int next;
};

int heads[MAXN];
Node pool[2 * MAXN];
int nn;
int dep[MAXN]; // 每个点的深度 
int anc[MAXN][20]; // anc[i][j]表示i点的2^j之前祖先点 
int lg2[MAXN]; // lg2[i]等于(log i) + 1 

void dfs(int u, int father) {
    dep[u] = dep[father] + 1;
    anc[u][0] = father;
    for (int i = 1; (1 << i) <= dep[u]; ++i) {
        anc[u][i] = anc[anc[u][i - 1]][i - 1];
    }
    for (int i = heads[u]; i; i = pool[i].next) {
        if (pool[i].v != father) {
            dfs(pool[i].v, u);
        }
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) {
        swap(x, y);
    }
    while (dep[x] > dep[y]) {
        x = anc[x][lg2[dep[x] - dep[y]] - 1];
    }
    if (x == y) return x;
    for (int i = lg2[dep[x]] - 1; i >= 0; --i) {
        if (anc[x][i] != anc[y][i]) {
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0];
}

// 加边函数
void addEdge(int u, int v) {
    pool[++nn].v = v;
    pool[nn].next = heads[u];
    heads[u] = nn;
} 

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b);
        addEdge(b, a);
    }

    for (int i = 1; i <= n; ++i) {
        lg2[i] = lg2[i - 1] + ((1 << lg2[i - 1]) == i);
    }

    dfs(1, 0);

    int a, b, c, t[3], f1, f2;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b >> c;
        t[0] = lca(a, b);
        t[1] = lca(b, c);
        t[2] = lca(a, c);
        f1 = 0; // 三个lca中（其中有两个重合），较深的那个
        for (int j = 0; j < 3; ++j) {
            if (dep[f1] < dep[t[j]]) {
                f1 = t[j];
            }
        } 
        f2 = f1; // 较浅的那个
        for (int j = 0; j < 3; ++j) {
            if (t[j] != f1) {
                f2 = t[j];
            }
        } 
        cout << f1 << " " << dep[a] + dep[b] + dep[c] - 2 * dep[f2] - dep[f1] << '\n';
    }

    return 0;
}

// 版本2
#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using std::swap;

const int MAXN = 500005;
int n, m;
int dep[MAXN], anc[MAXN][20];
vector<int> adj[MAXN];

void dfs(int u, int father) {
    dep[u] = dep[father] + 1;
    anc[u][0] = father;
    for (int i = 1; i < 20; ++i) {
        anc[u][i] = anc[anc[u][i - 1]][i - 1];
    }
    for (int i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (v == father) continue;
        dfs(v, u);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 19; i >= 0; --i) {
        if (dep[anc[x][i]] >= dep[y]) {
            x = anc[x][i];
        }
    }
    if (x == y) return x;
    for (int i = 19; i >= 0; --i) {
        if (anc[x][i] != anc[y][i]) {
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0];
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(1, 0);

    int a, b, c, t[3], f1, f2;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b >> c;
        t[0] = lca(a, b);
        t[1] = lca(b, c);
        t[2] = lca(a, c);
        f1 = 0; // 三个lca中（其中有两个重合），较深的那个
        for (int j = 0; j < 3; ++j) {
            if (dep[f1] < dep[t[j]]) {
                f1 = t[j];
            }
        } 
        f2 = f1; // 较浅的那个
        for (int j = 0; j < 3; ++j) {
            if (t[j] != f1) {
                f2 = t[j];
            }
        } 
        cout << f1 << " " << dep[a] + dep[b] + dep[c] - 2 * dep[f2] - dep[f1] << '\n';
    }

    return 0;
}