How far away ？

1. 题目解析

这是一道非常经典的图论题目，核心在于理解题目的隐含条件：

“n间房屋…任意两间房屋之间都存在唯一的一条简单路径”。

这不仅仅是一个图，而是一棵 树 (Tree)。

树的性质： $N$ 个节点， $N-1$ 条边，连通且无环。
路径距离：在树上，两个点 $u$ 和 $v$ 之间的唯一路径长度，可以通过 LCA (最近公共祖先) 快速求出。

公式推导

设 $Dist(u)$ 为节点 $u$ 到根节点（通常设为 1）的距离。

那么 $u$ 和 $v$ 之间的距离为：

Answer = Dist(u) + Dist(v) - 2 \times Dist(LCA(u, v))

算法流程：

建图：使用链式前向星存储无向带权图。
LCA 预处理：
- 选定 1 号点为根。
- DFS 遍历整棵树，计算出每个节点的深度 d[u]，倍增祖先 f[u][j]。
- 关键点：同时在 DFS 中计算每个节点到根的距离 dis[u]（带权距离）。
处理询问：对于每对 $(u, v)$ ，利用公式 $dis[u] + dis[v] - 2 \times dis[LCA(u, v)]$ 输出答案。
多组数据：注意 $T$ 组数据，每次必须清空图结构 (e.reset())。

2. 代码实现

使用了你的模板（LCA + LinkList），并进行了适配：

多组数据支持：添加了 solve() 函数和循环，每次调用 e.reset()。
距离计算：在 LCA 结构体中增加了 dis 数组，并在 dfs 时维护它。
语法糖：沿用了你喜欢的 for(auto [v, w] : e.adj(u)) 写法。

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-04 15:33:19
 */
#include <bits/stdc++.h>
using namespace std;

const int maxn = 40005; 
const int maxe = 80005; // 双向边，容量翻倍

int n, m;

// === 1. 链式前向星模板 ===
struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn], edge_cnt;
    
    linkList(){ reset(); }
    
    // 多组数据必须重置
    void reset() {
        edge_cnt = 0;
        memset(h, -1, sizeof(h));
    }
    
    void add2(int u, int v, int w) {
        e[edge_cnt] = {u, v, w, h[u]}; h[u] = edge_cnt++;
        e[edge_cnt] = {v, u, w, h[v]}; h[v] = edge_cnt++;
    }

    // 语法糖适配
#ifdef __cpp_range_based_for
    struct AdjIterator {
        int i; linkList* p;
        AdjIterator(linkList* p, int i) : p(p), i(i) {}
        AdjIterator& operator++() { i = p->e[i].next; return *this; }
        bool operator!=(const AdjIterator& oth) { return i != oth.i; }
        // 返回 {v, w}
        pair<int, int> operator*() { return {p->e[i].v, p->e[i].w}; }
    };
    struct BaseRange {
        int start; linkList* p;
        BaseRange(linkList* p, int start) : p(p), start(start) {}
        AdjIterator begin() { return AdjIterator(p, p->h[start]); }
        AdjIterator end()   { return AdjIterator(p, -1); }
    };
    BaseRange adj(int u) { return BaseRange(this, u); }
#endif
} e;

// === 2. LCA 模板 (支持距离查询) ===
const int MAXLOG = 20;   
struct LCA {
    int f[maxn][MAXLOG + 1];
    int d[maxn];      // 深度 (跳跃步数)
    int dis[maxn];    // **距离 (带权距离)**，用于求答案

    void init(int n, int root){
        // 从根节点开始，初始距离为 0
        dfs(root, 0, 1, 0); 
        
        // 倍增预处理
        for (int j = 1; j <= MAXLOG; ++j) {
            for (int i = 1; i <= n; ++i) {
                f[i][j] = f[ f[i][j-1] ][ j-1 ];
            }
        }
    }

    // DFS: 维护深度 d 和 带权距离 dis
    void dfs(int u, int fa, int depth, int current_dist) {
        d[u] = depth;
        f[u][0] = fa; 
        dis[u] = current_dist; // 记录该点到根的带权距离
        
        for (auto [v, w] : e.adj(u)) { 
            if (v != fa) {
                dfs(v, u, depth + 1, current_dist + w);
            }
        }
    }

    int ask(int u, int v) {
        if (d[u] < d[v]) swap(u, v);
        for (int i = MAXLOG; i >= 0; --i) {
            if (d[u] - (1 << i) >= d[v]) u = f[u][i];
        }
        if (u == v) return u;
        for (int i = MAXLOG; i >= 0; --i) {
            if (f[u][i] != f[v][i]) {
                u = f[u][i];
                v = f[v][i];
            }
        }
        return f[u][0];
    }
    
    // 新增：直接计算两点距离
    int get_dist(int u, int v) {
        int l = ask(u, v);
        return dis[u] + dis[v] - 2 * dis[l];
    }

} lca;

void solve() {
    // 多组数据，记得重置 linkList
    // LCA 的数组会被 init 覆盖，无需显式 memset，但图必须清空
    e.reset(); 
    
    cin >> n >> m;
    for(int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        e.add2(u, v, w);
    }
    
    lca.init(n, 1);
    
    for(int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        cout << lca.get_dist(u, v) << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    
    int t;
    cin >> t;
    while(t--) {
        solve();
        // 题目要求：每个测试用例结束后输出一个空行
        // (通常最后一个用例后是否需要看OJ判定，这里按照题目字面意思加)
        // 很多老题目POJ/UVa风格需要这个
        if (t >= 0) cout << "\n";
    }
    
    return 0;
}

目录

1. 题目解析

公式推导

2. 代码实现