思路与算法

三个城市的最优聚会点是三条两两路径的交汇点。先以1为根，迭代遍历记录父亲、深度和遍历顺序，逆序计算子树大小，选择子树最大的孩子为重儿子。再沿遍历顺序设置链头：重儿子继承父亲链头，其余孩子以自己为链头。这里只需链头信息，无须线段树。

求LCA时，若链头不同，就把较深链头所在的一点跳到其链头的父亲；最终处于同一重链时，深度较小者就是LCA。

对每次a、b、c，求x=lca(a,b)、y=lca(a,c)、z=lca(b,c)，在x、y、z中取最深者p作为聚会点。总费用等于三对距离之和的一半；每条边长度为1，展开可得depth[a]+depth[b]+depth[c]-depth[x]-depth[y]-depth[z]，复用已有三个LCA即可输出。使用连续边数组和缓冲读写处理50万规模。

正确性说明

重儿子是子树最大的孩子。每次从一个链头跳到父亲，都会越过一条轻边；链头较深一侧被移除的部分不可能含两点的公共祖先。不断上跳后，两点进入同链，该链上深度较小者正是最深公共祖先，所以重链LCA正确。

三条两两路径在树上交于唯一中位点p，重复端点允许某段长度为0。从p沿任一方向离开一条边，至多使一人的路程减1，却至少使另两人的路程各增1，因此总费用增加，p是唯一最优点。三个两两LCA中最深者恰为这个交点。

端点之间两两距离之和会把p到三个端点的分支分别计算两次，其一半就是最优费用。将每对距离按深度与LCA展开，得到代码中的六项加减式，故输出点和费用都正确。

复杂度

n点、m次聚会。邻接数组、父亲、深度、子树大小、重儿子和链头的初始化O(n)，正逆两次遍历及设置链头O(n)。跨越轻边后子树规模至少成倍变化，一次LCA至多经过O(log(n+1))条轻边；同链时直接比较深度。每次聚会3次LCA，总时间O(n+m log(n+1))，空间O(n)，包含初始化成本。

易错点

应比较LCA的深度，不能按编号大小选择聚会点。三点可以全部相同，此时输出该点和0。重儿子必须按子树大小选择，不能按深度或编号选，否则轻边数量界失效。设置链头必须在父亲已经处理后进行；显式遍历顺序满足此条件。重儿子哨兵0的子树大小设为0。所有遍历迭代执行，避免50万点长链递归溢出。深度及费用为O(n)，本题int足够；缓冲读入仅用于保证为正的规模和节点编号。

参考代码（C++11）

#include <algorithm>
#include <array>
#include <cstdio>
#include <vector>
using namespace std;
struct Input {
    static const int S = 1 << 16;
    char data[S];
    int at = 0, len = 0;
    int get() {
        if (at == len) {
            len = fread(data, 1, S, stdin);
            at = 0;
            if (!len)
                return EOF;
        }
        return data[at++];
    }
    int next() {
        int c = get();
        while (c <= 32 && c != EOF)
            c = get();
        int x = 0;
        while (c >= '0' && c <= '9') {
            x = x * 10 + c - '0';
            c = get();
        }
        return x;
    }
};
struct Output {
    static const int S = 1 << 16;
    char data[S];
    int at = 0;
    ~Output() {
        flush();
    }
    void flush() {
        fwrite(data, 1, at, stdout);
        at = 0;
    }
    void put(char c) {
        if (at == S)
            flush();
        data[at++] = c;
    }
    void number(int x, char end) {
        char digits[12];
        int k = 0;
        do {
            digits[k++] = char('0' + x % 10);
            x /= 10;
        } while (x);
        while (k)
            put(digits[--k]);
        put(end);
    }
};
int main() {
    Input in;
    Output out;
    int n = in.next(), q = in.next(), count = 0;
    vector<int> first(n + 1, -1), to(2 * (n - 1)), link(2 * (n - 1)), depth(n + 1);
    vector<int> parent(n + 1), size(n + 1, 1), heavy(n + 1), top(n + 1);
    size[0] = 0;
    auto add = [&](int u, int v) {
        to[count] = v;
        link[count] = first[u];
        first[u] = count++;
    };
    for (int i = 1; i < n; ++i) {
        int u = in.next(), v = in.next();
        add(u, v);
        add(v, u);
    }
    vector<int> order;
    order.reserve(n);
    order.push_back(1);
    for (int index = 0; index < n; ++index) {
        int u = order[index];
        for (int e = first[u]; e != -1; e = link[e]) {
            int v = to[e];
            if (v == parent[u])
                continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;
            order.push_back(v);
        }
    }
    for (int i = n - 1; i > 0; --i) {
        int u = order[i], p = parent[u];
        size[p] += size[u];
        if (size[u] > size[heavy[p]])
            heavy[p] = u;
    }
    top[1] = 1;
    for (int u : order) {
        for (int e = first[u]; e != -1; e = link[e]) {
            int v = to[e];
            if (parent[v] == u)
                top[v] = v == heavy[u] ? top[u] : v;
        }
    }
    auto lca = [&](int u, int v) {
        while (top[u] != top[v]) {
            if (depth[top[u]] > depth[top[v]])
                u = parent[top[u]];
            else
                v = parent[top[v]];
        }
        return depth[u] < depth[v] ? u : v;
    };
    while (q--) {
        int a = in.next(), b = in.next(), c = in.next();
        int x = lca(a, b), y = lca(a, c), z = lca(b, c), p = x;
        if (depth[y] > depth[p])
            p = y;
        if (depth[z] > depth[p])
            p = z;
        int cost = depth[a] + depth[b] + depth[c] - depth[x] - depth[y] - depth[z];
        out.number(p, ' ');
        out.number(cost, '\n');
    }
}