算法标签

树结构、LCA（最近公共祖先）、树上距离、路径构造、倍增法

题解

方法思路

要解决在树上找到满足给定距离要求的三个点的问题，我们可以利用树的直径相关性质以及倍增法来高效处理。

首先，通过两次深度优先搜索（DFS）找到树的直径的两个端点，确定树的直径路径。然后，预处理直径上的节点以及相关信息，包括每个节点的深度等。对于每次询问，根据三个距离 (x, y, z) 的大小关系，计算出三个点到直径上关键节点的距离，再利用预处理的信息找到满足条件的三个点 (u, v, w)。

具体步骤如下：

1. 找树的直径：通过两次 DFS 找到树的直径的两个端点，确定直径路径。
2. 预处理直径信息：记录直径上的节点，计算每个节点的深度等信息，并使用倍增法预处理区间最大值，以便快速查询。
3. 处理询问：对每次询问的三个距离，先排序确定大小关系，然后根据距离关系计算出三个点到直径上关键节点的距离，进而找到满足条件的三个点。

解决代码

#include <bits/stdc++.h>
#define pr pair<int,int>
#define eps 1e-10
#define int long long

using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();

    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;

        ch = getchar();
    }

    while (isdigit(ch)) {
        x = (x * 10 + ch - '0');
        ch = getchar();
    }

    return x * f;
}

const int N = 200005;
int head[N], to[N * 2], nxt[N * 2], cnt;
void add(int u, int v) {
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}

int n, q;
int fa[N], dep[N], lg[N], st[21][N], maxx[N], rt;
bool vis[N];
vector<int>awa, qwq[N];

void dfs(int now, int fath) {
    dep[now] = dep[fath] + 1;

    if (dep[now] > dep[rt])
        rt = now;

    fa[now] = fath;

    for (int i = head[now]; i; i = nxt[i]) {
        int v = to[i];

        if (v == fath || vis[v])
            continue;

        dfs(v, now);
    }
}

int a[4], p[4];

int query(int l, int r) {
    int len = lg[r - l + 1];
    return (maxx[st[len][l]] > maxx[st[len][r - (1 << len) + 1]]) ? st[len][l] : st[len][r - (1 << len) + 1];
}

void solve() {
    n = read();

    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        add(u, v), add(v, u);
    }

    rt = 0;
    dfs(1, 0);
    dfs(rt, 0);

    while (rt)
        vis[rt] = 1, awa.push_back(rt), rt = fa[rt];

    for (int i = 2; i <= n; i++)
        lg[i] = lg[i >> 1] + 1;

    for (int i = 0; i < (int)awa.size(); i++) {
        rt = 0;
        dep[0] = -1;
        dfs(awa[i], 0);
        st[0][i + 1] = i;
        maxx[i] = dep[rt];

        while (rt != awa[i])
            qwq[i].push_back(rt), rt = fa[rt];

        qwq[i].push_back(rt);
        reverse(qwq[i].begin(), qwq[i].end());
    }

    int len = awa.size();

    for (int i = 1; i <= 20; i++)
        for (int j = 1; j + (1 << i) - 1 <= len; j++)
            st[i][j] = (maxx[st[i - 1][j]] > maxx[st[i - 1][j + (1 << (i - 1))]]) ? st[i - 1][j] : st[i - 1][j + (1 << (i - 1))];

    q = read();

    while (q--) {
        for (int i = 1; i <= 3; i++)
            a[i] = read(), p[i] = i;

        sort(p + 1, p + 4, [&](int x, int y) {
            return a[x] > a[y];
        });
        int u, v, w;
        int dis1 = (a[p[2]] - a[p[3]] + a[p[1]]) / 2, dis2 = a[p[1]] - dis1;
        int ovo = query(dis1 + 1, len - dis2);

        if (maxx[ovo] >= a[p[2]] - dis1) {
            u = awa[ovo - dis1];
            v = awa[ovo + dis2];
            w = qwq[ovo][a[p[2]] - dis1];
        } else {
            ovo = query(dis2 + 1, len - dis1);
            u = awa[ovo + dis1];
            v = awa[ovo - dis2];
            w = qwq[ovo][a[p[2]] - dis1];
        }

        if (p[1] == 1 && p[2] == 2)
            printf("%lld %lld %lld\n", u, v, w);

        if (p[1] == 1 && p[2] == 3)
            printf("%lld %lld %lld\n", v, u, w);

        if (p[1] == 2 && p[2] == 1)
            printf("%lld %lld %lld\n", u, w, v);

        if (p[1] == 2 && p[2] == 3)
            printf("%lld %lld %lld\n", v, w, u);

        if (p[1] == 3 && p[2] == 1)
            printf("%lld %lld %lld\n", w, u, v);

        if (p[1] == 3 && p[2] == 2)
            printf("%lld %lld %lld\n", w, v, u);
    }
}

signed main() {
    int Tests = 1;

    while (Tests--)
        solve();

    return 0;
}

代码解释

1. 输入处理与邻接表构建：使用 read 函数快速读取输入，通过邻接表 head、to、nxt 构建树的结构。
2. 找树的直径：通过两次 DFS 找到树的直径的两个端点，第一次 DFS 找到距离节点 1 最远的节点，第二次 DFS 从该节点出发找到最远节点，确定直径。
3. 预处理直径信息：记录直径上的节点到数组 awa 中，计算每个直径节点的深度等信息，并使用倍增法预处理区间最大值数组 st，以便快速查询区间内的最大深度节点。
4. 处理询问：对每次询问的三个距离，先排序确定大小关系，计算出关键距离 dis1 和 dis2，通过查询预处理的倍增数组找到关键节点，进而确定满足条件的三个点 (u, v, w)，并根据排序后的距离顺序调整输出顺序。

这种方法利用树的直径和倍增法，能够在较大数据规模下高效处理每次询问，保证了算法的时间复杂度，适用于题目给定的所有数据范围。