#include #include #include #include using namespace std; const int NMAX = 100005; // 最大结点数 int n, q; vector tree[NMAX]; // 邻接表表示树 int x_coord[NMAX], y_coord[NMAX]; // 存储每个结点的坐标 // DFS 遍历：node 当前结点，pa...-Go服务器开发

这段代码是一个使用深度优先搜索（DFS）遍历树结构的程序，旨在计算树中任意两个节点之间的曼哈顿距离。我们将逐步分析代码的工作原理以及 x_coord 和 y_coord 数组的作用。

主要组成部分

常量与变量定义:
- const int NMAX = 100005;：定义最大节点数为 100005。
- int n, q;：n 是节点数，q 是查询次数。
- vector<int> tree[NMAX];：邻接表表示树，每个索引对应一个节点，存储其连接的其他节点。
- int x_coord[NMAX], y_coord[NMAX];：用于存储每个节点在平面上的坐标。

DFS 遍历函数：

void dfs(int node, int parent) {
   vector<int> children;
   for (int v : tree[node]) {
       if (v == parent) continue;
       children.push_back(v);
   }
   sort(children.begin(), children.end());
   for (int i = 0; i < children.size(); i++) {
       int child = children[i];
       if (i == 0) { 
           x_coord[child] = x_coord[node] - 1;
           y_coord[child] = y_coord[node] - 1;
       } else {      
           x_coord[child] = x_coord[node] + 1;
           y_coord[child] = y_coord[node] - 1;
       }
       dfs(child, node);
   }
}

DFS 函数解析

参数说明:
- node: 当前访问的节点。
- parent: 当前节点的父节点，用于防止返回到父节点。
步骤解释:
- 使用循环遍历当前节点的所有邻接点（子结点），并将其存入 children 向量，排除父结点以避免回溯。
- 将子结点按编号排序，以确保第一个子结点被视为“左儿子”。
- 遍历所有子结点：
  - 如果是第一个子结点，将其坐标设为 (x-1, y-1)，这样使得左儿子的坐标相对更低一点；
  - 如果是第二个子结点，将其坐标设为 (x+1, y-1)，使得右儿子的坐标比左儿子的高，但横向错开；
- 然后递归调用 DFS 来处理每个子结点。

坐标数组作用

坐标计算：
- 在 DFS 中，为了能用曼哈顿距离来计算任意两点之间的距离，需要给每个节点分配一个在二维平面上的坐标 (x,y)。
- 根结点（通常选择为编号为 1 的根）被初始化为 (0,0)。从根开始，左儿子向下移动至 (x−1,y−1)，右儿子则移动到 (x+1,y−1)。

曼哈顿距离计算

while(q--){
    int u, v;
    cin >> u >> v;
    int distance = abs(x_coord[u] - x_coord[v]) + abs(y_coord[u] - y_coord[v]);
    cout << distance << "\n";
}