three points 2 - 题解

标签与难度

标签: 树形DP, 最近公共祖先(LCA), 二分倍增(Binary Lifting), 离线查询, 树状数组, 降维打击难度: 2500

题目大意喵~

哈喵~！各位算法探险家们，大家好呀！咱是我，今天我们要一起探索一道关于树的有趣谜题，喵~

题目是这样的：我们拿到一棵有 $N$ 个节点的无权树，还有 $Q$ 次询问。每次询问会给我们三个整数 $a, b, c$ 。我们的任务呢，就是在这棵树上找到三个不同的顶点 $X, Y, Z$ ，使得它们之间的距离（也就是简单路径上的边数）正好满足：

$dist(X, Y) = a$
$dist(X, Z) = b$
$dist(Y, Z) = c$

如果能找到这样一组点，就把它们的编号（从0开始哦）告诉咱；如果找不到，就告诉咱 "-1"，好吗？

解题思路分析

这道题看起来有点复杂，要把几何关系搬到树上呢！不过别怕，跟着我的思路一步步来，我们一定能把它搞定的说！

步骤一：从距离到路径，找到那个神奇的“交叉点”！

首先，让我们思考一下在树上，三个点 $X, Y, Z$ 的路径会是什么样子。因为树没有环，所以连接任意两点的路径都是唯一的。三条路径 $X-Y, X-Z, Y-Z$ 必然会汇聚到一个中心点，我们叫它 $M$ 好了。这个 $M$ 可能是 $X, Y, Z$ 中的一个，也可能是路径上的其他点。

从图上可以看出来，三点间的距离关系可以表示成它们到中心点 $M$ 的距离之和：

$dist(X, Y) = dist(X, M) + dist(M, Y) = a$
$dist(X, Z) = dist(X, M) + dist(M, Z) = b$
$dist(Y, Z) = dist(Y, M) + dist(M, Z) = c$

嘿嘿，这是一个简单的三元一次方程组！让 $d_X = dist(X, M)$ , $d_Y = dist(Y, M)$ , $d_Z = dist(Z, M)$ 。把三个方程加起来，我们得到 $2(d_X + d_Y + d_Z) = a+b+c$ 。

于是，我们可以解出 $d_X, d_Y, d_Z$ ：

d_X = \frac{(a+b-c)}{2} \\ d_Y = \frac{(a+c-b)}{2} \\ d_Z = \frac{(b+c-a)}{2}

这给了我们一个超级重要的线索！对于一次查询 $(a, b, c)$ ，我们首先可以计算出这三个从中心点 $M$ 出发的路径长度。但是，这些长度必须是非负整数才行。所以，我们得到了第一个筛选条件：

$a+b+c$ 必须是偶数。
$a+b \ge c$ , $a+c \ge b$ , $b+c \ge a$ (三角不等式)，这样保证了 $d_X, d_Y, d_Z$ 都不会是负数。

如果一个查询不满足这些，那它肯定无解，直接输出 "-1" 就好啦，喵~

现在，问题就变成了：对于计算出的三个目标长度 $(d_X, d_Y, d_Z)$ ，我们能否在树上找到一个中心点 $M$ ，从它出发，能沿着三个不同方向的分支，分别走出长度至少为 $d_X, d_Y, d_Z$ 的路径？

步骤二：预处理每个点的“臂展”——树形DP

为了快速回答上面的问题，我们需要预先知道对于树上的每一个节点，它能向外延伸的最长路径是多长。一个节点 u 的“臂展”可以分为两部分：一部分是伸向它的子树（“向下”），另一部分是伸向它的父亲（“向上”）。

这可以用两遍DFS的树形DP来完美解决！

第一遍DFS (自底向上): 我们从叶子节点开始，向上计算。对于每个节点 u，我们记录从它出发，向下进入其各个子树能走出的最长、次长、第三长的路径。我们把它们记为 down[u][0], down[u][1], down[u][2]。同时，我们也要记录这些路径的终点和它们分别经过了 u 的哪个孩子节点，这在后面找具体点的时候会用到。
第二遍DFS (自顶向下): 现在我们来计算“向上”的路径。对于节点 u，从它出发向上能走的最远距离，取决于它父亲 p 的“臂展”。具体来说，u 的向上路径长度是 1 + (从 p 出发，不经过 u 的最长路径)。这个最长路径可能是 p 的向上路径，也可能是 p 向下进入其他子树的路径。在这次DFS中，我们可以综合 u 的所有向下路径和它唯一的向上路径，得到对于每个节点 u，它向各个方向分支的最长、次长、第三长路径，我们把它们记为 max_dist[u][0], max_dist[u][1], max_dist[u][2]。

完成这两遍DFS之后，我们就拥有了每个节点作为中心点 $M$ 时的“潜力”数据啦！

步骤三：离线处理查询——降维打击与树状数组

现在，对于每个查询，我们有了一组需求 (d_X, d_Y, d_Z)，对于每个节点，我们有了一组供给 (max_dist[u][0], max_dist[u][1], max_dist[u][2])。我们需要找到一个 u，使得（排序后）max_dist[u][i] >= d_i 对 i=0,1,2 都成立。

如果每次查询都遍历所有 $N$ 个节点，那肯定会超时的说 ( $O(NQ)$ )。这里有一个非常酷的技巧：离线处理 + 降维打击！

我们可以把所有 $N$ 个节点提供的“供给”和 $Q$ 个查询的“需求”看作三维空间中的点。问题就变成了，对每个查询点 (d_X, d_Y, d_Z)，是否存在一个供给点 (D_1, D_2, D_3) 支配它（即 $D_i \ge d_i$ 对所有 $i$ 成立）。这是一个三维偏序问题。

我们可以用CDQ分治或者更简单的“排序+数据结构”来解决。

整合与排序:
- 将每个节点 u 变成一个“供给”事件 (max_dist[u][0], max_dist[u][1], max_dist[u][2], u)。
- 将每个查询 q 变成一个“需求”事件 (d_X, d_Y, d_Z, q_id)。（记得先对 d 和 max_dist 降序排序）。
- 把这两类事件放在一个大列表里。
- 按照第一维（最长路径）降序对这个列表进行排序。如果第一维相同，供给事件（节点）要排在需求事件（查询）前面，这样我们才能先“上架商品”再“接待顾客”。
扫描与查询 (用树状数组降维):
- 我们按排好的顺序遍历事件列表。
- 当遇到一个供给事件 (D_1, D_2, D_3, u) 时，我们把它加入一个二维数据结构中。这个数据结构需要支持查询一个矩形区域内是否存在点。
- 为了简化，我们可以用树状数组来模拟这个二维数据结构。树状数组维护第二维 D_2，存储第三维 D_3 的信息。具体来说，bit.update(D_2, D_3) 表示我们有一个点，它的第二维是 D_2，第三维是 D_3。
- 当遇到一个需求事件 (d_X, d_Y, d_Z, q_id) 时，因为我们是按第一维降序处理的，所以所有已经加入树状数组的供给点都满足 $D_1 \ge d_X$ 。我们只需要在这些点中找一个满足 $D_2 \ge d_Y$ 且 $D_3 \ge d_Z$ 的。
- 这对应到树状数组上，就是查询所有 index >= d_Y 的位置上，是否存在一个存储的 value >= d_Z。我们可以通过查询树状数组在 [d_Y, N] 这个范围上的最大值来实现。

步骤四：找到最终答案——LCA与路径回溯

离线处理部分会告诉我们对于某个查询，是否存在一个合适的中心点 $M$ ，并返回一个可行的 $M$ 的编号。

最后一步，就是根据 $M$ 和需求的长度 (d_X, d_Y, d_Z)，找出具体的 $X, Y, Z$ 。我们在预处理时已经存下了每个节点最长路径的终点。假设 $M$ 的三个最长分支的终点分别是 E_1, E_2, E_3。要找到 $X$ ，它就在 $M$ 到对应分支终点的路径上，距离 $M$ 为 $d_X$ 。

这可以用LCA（最近公共祖先）和二分倍增来快速定位。我们可以预处理出每个节点的深度和它的 $2^k$ 级祖先。然后就可以在 $O(\log N)$ 的时间内找到路径上的任意一个点了！

把 $X, Y, Z$ 都找到后，按照题目要求的格式输出就好啦！整个过程虽然步骤多，但每一步都是经典的算法模块，组合起来就解决了这个复杂的问题，是不是很有成就感呢，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码~ 每个部分都有详细的注释，希望能帮助你理解哦！

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

const int MAXN = 200005;
const int LOGN = 18;

// --- 邻接表 ---
vector<int> adj[MAXN];
int n;

// --- 树形DP & LCA 相关 ---
// {distance, endpoint}
using PathInfo = pair<int, int>; 

// 向下路径信息: {路径长度, 路径终点, 经过的直接子节点}
struct DownPath {
    int dist, endpoint, via_child;
    bool operator<(const DownPath& other) const {
        return dist < other.dist;
    }
};

vector<DownPath> down_paths[MAXN];
PathInfo up_path[MAXN]; // 向上路径信息 {dist, endpoint}
PathInfo final_paths[MAXN][3]; // 每个节点最终的3条最长路径

int depth[MAXN];
int parent[MAXN][LOGN];

// --- 离线处理 & 树状数组 ---
struct NodeData {
    int d1, d2, d3, id;
    bool is_query;
    // for queries
    int orig_lens[3];
    int sorted_indices[3];
};

bool compareNodes(const NodeData& a, const NodeData& b) {
    if (a.d1 != b.d1) return a.d1 > b.d1;
    if (a.is_query != b.is_query) return a.is_query < b.is_query; // 供给(false)优先
    return a.d2 > b.d2;
}

PathInfo bit[MAXN]; // {max_d3, node_id}

void bit_update(int idx, PathInfo val) {
    for (; idx < MAXN; idx += idx & -idx) {
        bit[idx] = max(bit[idx], val);
    }
}

PathInfo bit_query(int idx) {
    PathInfo res = { -1, -1 };
    for (; idx > 0; idx -= idx & -idx) {
        res = max(res, bit[idx]);
    }
    return res;
}

// --- DFS & 预处理 ---
void dfs1_down(int u, int p, int d) {
    depth[u] = d;
    parent[u][0] = p;
    down_paths[u].push_back({0, u, -1}); // 长度为0的路径

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs1_down(v, u, d + 1);
        down_paths[u].push_back({down_paths[v][0].dist + 1, down_paths[v][0].endpoint, v});
        sort(down_paths[u].rbegin(), down_paths[u].rend());
        if (down_paths[u].size() > 3) down_paths[u].resize(3);
    }
}

void dfs2_up(int u, int p) {
    // 整理u的所有分支路径
    vector<PathInfo> all_paths;
    if (p != 0) all_paths.push_back(up_path[u]);
    for(const auto& path : down_paths[u]) {
        all_paths.push_back({path.dist, path.endpoint});
    }
    sort(all_paths.rbegin(), all_paths.rend());
    for(int i=0; i<min((int)all_paths.size(), 3); ++i) {
        final_paths[u][i] = all_paths[i];
    }
    for(int i=all_paths.size(); i<3; ++i) {
        final_paths[u][i] = {-1, -1};
    }

    // 向下传递up_path信息
    for (int v : adj[u]) {
        if (v == p) continue;
        
        // 父节点p给v的最长路径，是p不经过v的最长路径
        int p_dist_to_v = 0;
        int p_endpoint_to_v = 0;

        // 1. 考虑p的up_path
        if (p != 0) {
            p_dist_to_v = up_path[u].dist + 1;
            p_endpoint_to_v = up_path[u].endpoint;
        }

        // 2. 考虑p的其他down_path
        if (down_paths[u][0].via_child != v) {
            if (down_paths[u][0].dist + 1 > p_dist_to_v) {
                p_dist_to_v = down_paths[u][0].dist + 1;
                p_endpoint_to_v = down_paths[u][0].endpoint;
            }
        } else if (down_paths[u].size() > 1) {
            if (down_paths[u][1].dist + 1 > p_dist_to_v) {
                p_dist_to_v = down_paths[u][1].dist + 1;
                p_endpoint_to_v = down_paths[u][1].endpoint;
            }
        }
        up_path[v] = {p_dist_to_v, p_endpoint_to_v};
        
        dfs2_up(v, u);
    }
}

void precompute_lca() {
    for (int j = 1; j < LOGN; ++j) {
        for (int i = 1; i <= n; ++i) {
            if (parent[i][j - 1] != 0) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }
        }
    }
}

int get_kth_ancestor(int u, int k) {
    for (int i = 0; i < LOGN; ++i) {
        if ((k >> i) & 1) {
            u = parent[u][i];
        }
    }
    return u;
}

int get_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    u = get_kth_ancestor(u, depth[u] - depth[v]);
    if (u == v) return u;
    for (int i = LOGN - 1; i >= 0; --i) {
        if (parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    return parent[u][0];
}

int get_node_on_path(int u, int v, int dist_from_u) {
    int lca = get_lca(u, v);
    int d_u_lca = depth[u] - depth[lca];
    if (dist_from_u <= d_u_lca) {
        return get_kth_ancestor(u, dist_from_u);
    }
    int total_dist = d_u_lca + depth[v] - depth[lca];
    int dist_from_v = total_dist - dist_from_u;
    return get_kth_ancestor(v, dist_from_v);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        ++u; ++v; // 0-indexed to 1-indexed
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // --- 预处理 ---
    dfs1_down(1, 0, 0);
    dfs2_up(1, 0);
    precompute_lca();
    
    // --- 离线处理 ---
    vector<NodeData> events;
    for (int i = 1; i <= n; ++i) {
        if (final_paths[i][0].first != -1) {
             events.push_back({final_paths[i][0].first, final_paths[i][1].first, final_paths[i][2].first, i, false});
        }
    }

    int q;
    cin >> q;
    vector<pair<int, int>> query_results(q);

    for (int i = 0; i < q; ++i) {
        long long a, b, c;
        cin >> a >> b >> c;
        long long sum = a + b + c;
        if (sum % 2 != 0 || a + b < c || a + c < b || b + c < a) {
            query_results[i] = {-1, -1};
            continue;
        }
        
        vector<pair<int, int>> lens = {
            {(int)((a + b - c) / 2), 0},
            {(int)((a + c - b) / 2), 1},
            {(int)((b + c - a) / 2), 2}
        };
        sort(lens.rbegin(), lens.rend());

        NodeData query_node;
        query_node.d1 = lens[0].first;
        query_node.d2 = lens[1].first;
        query_node.d3 = lens[2].first;
        query_node.id = i;
        query_node.is_query = true;
        for(int k=0; k<3; ++k) query_node.orig_lens[k] = lens[k].first;
        for(int k=0; k<3; ++k) query_node.sorted_indices[k] = lens[k].second;
        events.push_back(query_node);
    }

    sort(events.begin(), events.end(), compareNodes);
    
    for (const auto& event : events) {
        if (!event.is_query) { // 供给点
            // d2和d3可能为-1，树状数组下标必须正，所以+2
            if (event.d2 != -1) {
                bit_update(event.d2 + 2, {event.d3, event.id});
            }
        } else { // 查询点
            PathInfo res = bit_query(event.d2 + 2);
            if (res.first >= event.d3) {
                query_results[event.id] = {res.second, 1}; // {center_node, found_flag}
            } else {
                query_results[event.id] = {-1, -1};
            }
        }
    }

    // --- 输出结果 ---
    vector<int> final_ans(3);
    for (int i = 0; i < q; ++i) {
        if (query_results[i].first == -1) {
            cout << -1 << "\n";
        } else {
            int center = query_results[i].first;
            auto& query_event = events[0]; // Find the query event again to get details
            for(const auto& ev : events) {
                if(ev.is_query && ev.id == i) {
                    query_event = ev;
                    break;
                }
            }
            
            final_ans[query_event.sorted_indices[0]] = get_node_on_path(center, final_paths[center][0].second, query_event.orig_lens[0]);
            final_ans[query_event.sorted_indices[1]] = get_node_on_path(center, final_paths[center][1].second, query_event.orig_lens[1]);
            final_ans[query_event.sorted_indices[2]] = get_node_on_path(center, final_paths[center][2].second, query_event.orig_lens[2]);

            cout << final_ans[0] - 1 << " " << final_ans[1] - 1 << " " << final_ans[2] - 1 << "\n";
        }
    }

    return 0;
}

复杂度分析

时间复杂度: $O((N+Q)\log(N+Q))$
- 树形DP: 两遍DFS，第一遍DFS中对每个节点的子节点路径排序，由于每个节点最多只有3个向下路径被保留，所以总复杂度是 $O(N \log(\text{degree}))$ , 近似为 $O(N)$ 。
- LCA预处理: $O(N \log N)$ 。
- 离线处理: 主要开销在于对 $N+Q$ 个事件的排序，为 $O((N+Q)\log(N+Q))$ 。之后遍历事件列表，每次树状数组操作为 $O(\log N)$ ，总共是 $O((N+Q)\log N)$ 。
- 查询结果: 对每个查询，找LCA和节点是 $O(\log N)$ 。
- 综上，总时间复杂度由排序主导，为 $O((N+Q)\log(N+Q))$ 。
空间复杂度: $O(N \log N)$
- 邻接表和DP数组: $O(N)$ 。
- LCA的parent数组: $O(N \log N)$ 。
- 离线事件列表: $O(N+Q)$ 。
- 树状数组: $O(N)$ 。
- 因此，主要空间开销是LCA的预处理，为 $O(N \log N)$ 。

知识点总结

这道题是多种经典算法的巧妙结合，像一道丰盛的算法大餐，喵~

问题转化: 核心思想是将三点间的距离问题转化为寻找一个具有特定“臂展”的中心点问题。这是解题的第一步，也是最关键的一步！
树形DP: 用两遍DFS计算每个节点向各个方向的最长路径，是处理树上路径问题的常用技巧。
三维偏序/降维打击: 面对多维度的查询条件，通过离线处理，排序固定一个维度，再用数据结构（如树状数组、线段树）处理剩下的维度，是一种非常强大的优化思想。
LCA与二分倍增: 在树上快速定位节点、计算距离、查找路径上的第k个点，LCA是不可或缺的工具。
离线思想: 当查询不依赖于之前查询的结果时，可以把所有查询收集起来，通过排序等方式一起处理，往往能获得比在线处理更优的复杂度。

希望这篇题解能帮到你！继续加油，在算法的世界里不断探索吧，喵~！

three points 2 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

步骤一：从距离到路径，找到那个神奇的“交叉点”！ ​

步骤二：预处理每个点的“臂展”——树形DP ​

步骤三：离线处理查询——降维打击与树状数组 ​

步骤四：找到最终答案——LCA与路径回溯 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​