题目分析

本题给定一棵 (n) 个点的树，要求处理多次查询，每次查询给出两个点，需要计算并输出这两点之间的最短距离。树中的边是无向的，且每个节点编号在 (1) 到 (n) 之间 ，边带有长度信息。

代码逐段分析

1. 头文件和全局变量

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 10010, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int p[N];
int res[M];
int st[N];
vector<PII> query[N];

- 引入了输入输出、字符串处理、算法和向量相关的头文件，并使用标准命名空间。
- 定义 `PII` 为 `pair<int, int>` 的别名，方便后续使用。
- 定义常量 `N` 表示节点的最大数量，`M` 表示边的最大数量（无向图边数最多为节点数的两倍）。
- `n` 记录树的节点数，`m` 记录查询的次数。
- `h[N]`、`e[M]`、`w[M]`、`ne[M]` 和 `idx` 用于构建带权邻接表存储树结构，`w[M]` 存储边的权重。
- `dist[N]` 记录从根节点到每个节点的距离。
- `p[N]` 用于并查集，记录每个节点的父节点。
- `res[M]` 存储每个查询的结果。
- `st[N]` 用于标记节点的状态（`1` 表示正在访问，`2` 表示已访问完其子节点）。
- `query[N]` 是一个向量数组，`query[u]` 存储与节点 `u` 相关的查询，每个查询用 `PII` 表示，`first` 是查询的另一个点，`second` 是查询编号。

1. 添加边的函数 add(int a, int b, int c)

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

该函数用于在邻接表中添加一条从节点 a 到节点 b，权重为 c 的边。

1. 深度优先搜索函数 dfs(int u, int fa)

void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}

- 从节点 `u` 开始进行深度优先搜索，`fa` 是节点 `u` 的父节点，用于防止搜索回父节点。
- 遍历节点 `u` 的所有邻接节点 `j`，如果 `j` 不是 `u` 的父节点，更新节点 `j` 到根节点的距离为节点 `u` 到根节点的距离加上边 `(u, j)` 的权重，并递归对节点 `j` 进行深度优先搜索。

1. 并查集查找函数 find(int x)

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

该函数用于在并查集中查找节点 x 的根节点，同时进行路径压缩。

1. Tarjan 算法函数 tarjan(int u)

void tarjan(int u)
{
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            tarjan(j);
            p[j] = u;
        }
    }

    for (auto item : query[u])
    {
        int y = item.first, id = item.second;
        if (st[y] == 2)
        {
            int anc = find(y);
            res[id] = dist[u] + dist[y] - dist[anc] * 2;
        }
    }

    st[u] = 2;
}

- 首先将节点 `u` 的状态标记为正在访问（`st[u] = 1`）。
- 遍历节点 `u` 的所有邻接节点 `j`，如果 `j` 未被访问，对 `j` 进行 Tarjan 算法递归处理，并将 `j` 的父节点设为 `u`。
- 遍历与节点 `u` 相关的所有查询 `item`，如果查询的另一个节点 `y` 的状态为已访问完其子节点（`st[y] = 2`），通过并查集找到 `u` 和 `y` 的最近公共祖先 `anc`，计算并存储两点之间的距离 `res[id]`，距离公式为 `dist[u] + dist[y] - dist[anc] * 2`。
- 最后将节点 `u` 的状态标记为已访问完其子节点（`st[u] = 2`）。

1. 主函数 main()

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a != b)
        {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
    }

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    dfs(1, -1);
    tarjan(1);

    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);

    return 0;
}

- 读取树的节点数 `n` 和查询次数 `m`，初始化邻接表头数组 `h` 为 `-1`。
- 循环读取 `n - 1` 条边的信息，构建树的邻接表。
- 循环读取 `m` 次查询，将每个查询分别添加到两个节点的查询向量中。
- 初始化并查集，每个节点的父节点设为自身。
- 从节点 `1` 开始进行深度优先搜索，计算每个节点到根节点的距离。
- 从节点 `1` 开始进行 Tarjan 算法，处理所有查询并计算最短距离。
- 输出每个查询的结果。

时间复杂度和空间复杂度分析

• 时间复杂度：
  • 构建树的邻接表，时间复杂度为 (O(n))。
  • 处理查询，将查询添加到对应节点的向量中，时间复杂度为 (O(m))。
  • 深度优先搜索 dfs 遍历树，时间复杂度为 (O(n))。
  • Tarjan 算法，每个节点和每条边最多被访问一次，时间复杂度为 (O(n + m))。
  • 总体时间复杂度为 (O(n + m))。
• 空间复杂度：
  • 邻接表存储树结构，空间复杂度为 (O(n + m))（这里边数 (m = n - 1)，所以为 (O(n))）。
  • 存储查询的向量数组 query[N]，最坏情况下空间复杂度为 (O(m))。
  • 其他辅助数组，如 dist[N]、p[N]、res[M]、st[N] 等，空间复杂度为 (O(n))。
  • 总体空间复杂度为 (O(n + m))。