#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // 构造函数：用值初始化，无子节点
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// 前序遍历 — O(N) 时间，O(H) 空间（H = 高度）
// 访问顺序：根，左子树，右子树
void preorder(TreeNode* root) {
    if (root == nullptr) return;   // 基础情况
    cout << root->val << " ";      // 先处理根
    preorder(root->left);          // 然后左子树
    preorder(root->right);         // 然后右子树
}

// 对于树：    [5]
//             /    \
//           [3]    [8]
//          /   \
//        [1]   [4]
// 前序：5 3 1 4 8

// 前序遍历迭代版
void preorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> stk;
    stk.push(root);

    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        cout << node->val << " ";    // 处理当前节点

        // 先压右子节点（这样左子节点先被处理——LIFO！）
        if (node->right) stk.push(node->right);
        if (node->left)  stk.push(node->left);
    }
}

// 中序遍历 — O(N) 时间
// 访问顺序：左子树，根，右子树
// 关键性质：BST 的中序遍历产生有序输出！
void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);           // 先左子树
    cout << root->val << " ";      // 然后根
    inorder(root->right);          // 然后右子树
}

// 对 BST（值 {1, 3, 4, 5, 8}）：
// 中序：1 3 4 5 8  ← 有序！这是 BST 最重要的性质

// 中序遍历迭代版
void inorderIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* curr = root;

    while (curr != nullptr || !stk.empty()) {
        // 尽量向左走
        while (curr != nullptr) {
            stk.push(curr);
            curr = curr->left;
        }
        // 处理最左侧未处理的节点
        curr = stk.top(); stk.pop();
        cout << curr->val << " ";

        // 转向右子树
        curr = curr->right;
    }
}

// 后序遍历 — O(N) 时间
// 访问顺序：左子树，右子树，根
// 用于：删除树、求值表达式树
void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);         // 先左子树
    postorder(root->right);        // 然后右子树
    cout << root->val << " ";      // 根最后
}

// ── 用后序遍历清理内存 ──
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);   // 先删左子树
    deleteTree(root->right);  // 再删右子树
    delete root;              // 最后删这个节点（安全：子节点已删）
}

// 层序遍历（BFS）— O(N) 时间，O(W) 空间（W = 最大层宽）
// 使用队列：逐层处理节点
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();  // 当前层的节点数

        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            cout << node->val << " ";

            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << "\n";  // 层间换行
    }
}

// 对 BST [5, 3, 8, 1, 4]：
// 第 0 层：5
// 第 1 层：3 8
// 第 2 层：1 4

// 树的高度 — O(N) 时间，O(H) 递归栈空间
// 高度 = 最长的根到叶路径的长度
// 约定：空树高度 = -1，叶节点高度 = 0
int height(TreeNode* root) {
    if (root == nullptr) return -1;  // 空子树高度 -1

    int leftHeight  = height(root->left);   // 左子树高度
    int rightHeight = height(root->right);  // 右子树高度

    return 1 + max(leftHeight, rightHeight);  // +1 表示当前节点
}

// 检查平衡 BST — O(N) 时间
// 不平衡时返回 -1，否则返回子树高度
int checkBalanced(TreeNode* root) {
    if (root == nullptr) return 0;  // 空树平衡，高度 0

    int leftH = checkBalanced(root->left);
    if (leftH == -1) return -1;     // 左子树不平衡

    int rightH = checkBalanced(root->right);
    if (rightH == -1) return -1;    // 右子树不平衡

    // 检查当前节点的平衡：高度差不超过 1
    if (abs(leftH - rightH) > 1) return -1;  // 不平衡！

    return 1 + max(leftH, rightH);   // 平衡时返回高度
}

bool isBalanced(TreeNode* root) {
    return checkBalanced(root) != -1;
}

// 节点计数 — O(N)
int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// 专门统计叶节点
int countLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;  // 叶节点！
    return countLeaves(root->left) + countLeaves(root->right);
}

// BST 搜索 — 平均 O(log N)，最坏 O(N)
// 返回值为 'target' 的节点指针，找不到返回 nullptr
TreeNode* search(TreeNode* root, int target) {
    // 基础情况：空树或找到目标
    if (root == nullptr || root->val == target) {
        return root;
    }
    // BST 性质：target 更小则向左
    if (target < root->val) {
        return search(root->left, target);
    }
    // target 更大则向右
    return search(root->right, target);
}

// BST 插入 — 平均 O(log N)
// 返回子树（可能是新的）的根节点
TreeNode* insert(TreeNode* root, int val) {
    // 到达空位时，在此创建新节点
    if (root == nullptr) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);   // 递归向左
    } else if (val > root->val) {
        root->right = insert(root->right, val); // 递归向右
    }
    // val == root->val：重复值，忽略（或按需处理）
    return root;
}

// 用法：
// TreeNode* root = nullptr;
// root = insert(root, 5);
// root = insert(root, 3);
// root = insert(root, 8);

// BST 删除 — 平均 O(log N)
// 辅助函数：找子树中最小节点
TreeNode* findMin(TreeNode* node) {
    while (node->left != nullptr) node = node->left;
    return node;
}

// 从以 'root' 为根的树中删除值为 'val' 的节点
TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == nullptr) return nullptr;  // 值未找到

    if (val < root->val) {
        // 情况：目标在左子树
        root->left = deleteNode(root->left, val);
    } else if (val > root->val) {
        // 情况：目标在右子树
        root->right = deleteNode(root->right, val);
    } else {
        // 找到要删除的节点！

        // 情况一：无子节点（叶节点）
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }
        // 情况二A：只有右子节点
        else if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        // 情况二B：只有左子节点
        else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        // 情况三：有两个子节点——用中序后继替换
        else {
            TreeNode* successor = findMin(root->right);  // 右子树中最小
            root->val = successor->val;                  // 复制后继的值
            root->right = deleteNode(root->right, successor->val);  // 删除后继
        }
    }
    return root;
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

struct BST {
    TreeNode* root;
    BST() : root(nullptr) {}

    // ── 插入 ──
    TreeNode* _insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);
        if (val < node->val) node->left  = _insert(node->left,  val);
        else if (val > node->val) node->right = _insert(node->right, val);
        return node;
    }
    void insert(int val) { root = _insert(root, val); }

    // ── 搜索 ──
    bool search(int val) {
        TreeNode* curr = root;
        while (curr) {
            if (val == curr->val) return true;
            curr = (val < curr->val) ? curr->left : curr->right;
        }
        return false;
    }

    // ── 中序遍历（有序输出） ──
    void _inorder(TreeNode* node, vector<int>& result) {
        if (!node) return;
        _inorder(node->left, result);
        result.push_back(node->val);
        _inorder(node->right, result);
    }
    vector<int> getSorted() {
        vector<int> result;
        _inorder(root, result);
        return result;
    }

    // ── 高度 ──
    int _height(TreeNode* node) {
        if (!node) return -1;
        return 1 + max(_height(node->left), _height(node->right));
    }
    int height() { return _height(root); }
};

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

    BST bst;
    vector<int> vals = {5, 3, 8, 1, 4, 7, 10};
    for (int v : vals) bst.insert(v);

    cout << "有序输出：";
    for (int v : bst.getSorted()) cout << v << " ";
    cout << "\n";
    // 输出：1 3 4 5 7 8 10

    cout << "高度：" << bst.height() << "\n";  // 2
    cout << "搜索 4：" << bst.search(4) << "\n";  // 1（真）
    cout << "搜索 6：" << bst.search(6) << "\n";  // 0（假）

    return 0;
}

前序：[3, 9, 20, 15, 7]
中序：[9, 3, 15, 20, 7]

第一步：前序第一个 = 3，所以根是 3
第二步：在中序里找 3，把它左边和右边分开
        [9, | 3 |, 15, 20, 7]
         ↑左子树  ↑  ↑右子树↑

第三步：递归处理左子树和右子树
        左子树：前序 [9]，中序 [9] → 叶节点 9
        右子树：前序 [20, 15, 7]，中序 [15, 20, 7]
                → 根 20，左 15，右 7

// 从前序 + 中序重建树 — O(N^2) 朴素版
TreeNode* build(vector<int>& pre, int preL, int preR,
                vector<int>& in,  int inL,  int inR) {
    if (preL > preR) return nullptr;

    int rootVal = pre[preL];  // 前序第一个 = 根
    TreeNode* root = new TreeNode(rootVal);

    // 在中序数组中找根
    int rootIdx = inL;
    while (in[rootIdx] != rootVal) rootIdx++;

    int leftSize = rootIdx - inL;  // 左子树节点数

    // 递归构建左右子树
    root->left  = build(pre, preL+1, preL+leftSize, in, inL, rootIdx-1);
    root->right = build(pre, preL+leftSize+1, preR, in, rootIdx+1, inR);

    return root;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();
    return build(preorder, 0, n-1, inorder, 0, n-1);
}

          [1]
         /    \
       [2]    [3]
      /   \      \
    [4]   [5]   [6]
   /
  [7]

LCA(4, 5) = 2     （4 和 5 都是 2 的后代）
LCA(4, 6) = 1     （最深公共祖先是根 1）
LCA(2, 4) = 2     （节点 2 是 4 的祖先，也是自身的祖先）

// LCA 暴力法 — 每次查询 O(N)
// 策略：找从根到每个节点的路径，然后找最后一个公共节点

// 第一步：找从根到目标节点的路径
bool findPath(TreeNode* root, int target, vector<int>& path) {
    if (root == nullptr) return false;

    path.push_back(root->val);  // 将当前节点加入路径

    if (root->val == target) return true;  // 找到目标！

    // 先尝试左子树，再尝试右子树
    if (findPath(root->left, target, path)) return true;
    if (findPath(root->right, target, path)) return true;

    path.pop_back();  // 回溯：目标不在这个子树中
    return false;
}

// 第二步：用两条路径找 LCA
int lca(TreeNode* root, int u, int v) {
    vector<int> pathU, pathV;

    findPath(root, u, pathU);   // 从根到 u 的路径
    findPath(root, v, pathV);   // 从根到 v 的路径

    // 找两条路径的最后一个公共节点
    int result = root->val;
    int minLen = min(pathU.size(), pathV.size());

    for (int i = 0; i < minLen; i++) {
        if (pathU[i] == pathV[i]) {
            result = pathU[i];  // 仍然公共
        } else {
            break;  // 分叉了
        }
    }
    return result;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005, LOG = 20;
vector<int> adj[MAXN];
int depth[MAXN], anc[MAXN][LOG];

// DFS 建树，同时计算 anc[v][k]
void dfs(int u, int par, int d) {
    depth[u] = d;
    anc[u][0] = par;  // 直接父节点
    for (int k = 1; k < LOG; k++)
        anc[u][k] = anc[anc[u][k-1]][k-1];  // 倍增构建
    for (int v : adj[u])
        if (v != par) dfs(v, u, d + 1);
}

// O(log N) LCA 查询
int lca(int u, int v) {
    // 步骤1：把深度更大的节点提升到与另一个相同深度
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOG; k++)
        if ((diff >> k) & 1) u = anc[u][k];
    
    // 步骤2：两个在相同深度的节点同步上跳，直到相遇
    if (u == v) return u;  // 其中一个本来就是另一个的祖先
    for (int k = LOG - 1; k >= 0; k--)
        if (anc[u][k] != anc[v][k]) {
            u = anc[u][k];
            v = anc[v][k];
        }
    return anc[u][0];  // 此时 u, v 的父节点就是 LCA
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1, 0);  // 根为1，根的父节点设为自身
    while (q--) {
        int u, v; cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}

          1
         / \
        2   3
       / \
      4   5

DFS 顺序：1(in=1) → 2(in=2) → 4(in=3,out=3) → 5(in=4,out=4) → 2(out=4) → 3(in=5,out=5) → 1(out=5)

in  = [_, 1, 2, 5, 3, 4]  （节点1~5的进入时间）
out = [_, 5, 4, 5, 3, 4]  （节点1~5的退出时间）

节点2的子树 = [in[2], out[2]] = [2, 4] = {节点2, 4, 5} ✓

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> children[MAXN];
int val[MAXN];
int in_time[MAXN], out_time[MAXN], timer_val = 0;
int euler_arr[MAXN];   // euler_arr[in_time[u]] = val[u]

void dfs_euler(int u, int parent) {
    in_time[u] = ++timer_val;       // 进入：记录时间戳
    euler_arr[timer_val] = val[u];  // 在展平数组中记录值
    
    for (int v : children[u]) {
        if (v != parent) dfs_euler(v, u);
    }
    
    out_time[u] = timer_val;        // 退出：记录最终时间戳
}

// 查询节点 u 的子树中所有值的和
// 用前缀和数组 prefix 预处理 euler_arr
int subtree_sum(int u, int prefix[]) {
    return prefix[out_time[u]] - prefix[in_time[u] - 1];
}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        children[u].push_back(v);
        children[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> val[i];
    
    dfs_euler(1, -1);  // 从根 1 开始
    
    // 构建前缀和
    int prefix[MAXN] = {};
    for (int i = 1; i <= n; i++)
        prefix[i] = prefix[i-1] + euler_arr[i];
    
    // 查询节点 u 的子树和
    int u; cin >> u;
    cout << subtree_sum(u, prefix) << "\n";
    return 0;
}

// 奶牛家族树 — 深度查询
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> children[MAXN];  // 邻接表：children[i] = i 的子节点列表
int depth[MAXN];             // depth[i] = 节点 i 的深度

// DFS 计算深度
void dfs(int node, int d) {
    depth[node] = d;
    for (int child : children[node]) {
        dfs(child, d + 1);  // 子节点深度 +1
    }
}

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

    int n, m;
    cin >> n >> m;

    for (int i = 2; i <= n; i++) {
        int par;
        cin >> par;
        children[par].push_back(i);  // par 是 i 的父节点
    }

    dfs(1, 0);  // 从根（奶牛 1）以深度 0 开始 DFS

    while (m--) {
        int x;
        cin >> x;
        cout << depth[x] << "\n";
    }

    return 0;
}
// 时间：O(N + M)
// 空间：O(N)

// ❌ 错误：没有空指针检查！
void inorder(TreeNode* root) {
    inorder(root->left);  // root 为空时崩溃
    cout << root->val;
    inorder(root->right);
}

// ✅ 正确：始终先检查空指针
void inorder(TreeNode* root) {
    if (root == nullptr) return;  // ← 关键！
    inorder(root->left);
    cout << root->val;
    inorder(root->right);
}

// ❌ 危险：10^5 个节点的退化树（倾斜）
// 递归深度 = 10^5，默认栈 ~8MB，约 10^4~10^5 时溢出！

// ✅ 安全：大树用迭代
void dfsIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    if (root) stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        process(node);
        if (node->right) stk.push(node->right);
        if (node->left)  stk.push(node->left);
    }
}

核心思路： 向下传递允许的 (min, max) 范围，每个节点必须严格在其范围内。

#include <bits/stdc++.h>
using namespace std;
struct TreeNode { int val; TreeNode *left, *right; };

bool isValidBST(TreeNode* root, long long lo, long long hi) {
    if (!root) return true;
    if (root->val <= lo || root->val >= hi) return false;
    return isValidBST(root->left, lo, root->val)
        && isValidBST(root->right, root->val, hi);
}
// 用法：isValidBST(root, LLONG_MIN, LLONG_MAX);

为什么需要最小/最大边界？ 因为根的右子树中的某个节点，即使是某个祖先的左子节点，也必须 > 根。只传直接父节点不够。

复杂度： O(N) 时间，O(H) 递归栈。

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        if (--k == 0) return cur->val;
        cur = cur->right;
    }
    return -1;
}

复杂度： O(H + K) —— 对小 K 远优于 O(N)。

核心思路： 后序 DFS。每个节点计算：(a) 供父节点使用的自身高度；(b) 经过它的最优路径（更新全局答案）。

int diameter = 0;
int height(TreeNode* root) {
    if (!root) return 0;
    int L = height(root->left);
    int R = height(root->right);
    diameter = max(diameter, L + R);  // 经过该节点的路径：左边 L 条边 + 右边 R 条边
    return 1 + max(L, R);              // 返回给父节点的高度
}
// 答案：diameter（边数）。若要节点数，diameter+1。

为什么有效？ 直径必然经过某个「顶点」节点——路径上的最高节点。该顶点的贡献 = height(左) + height(右)。我们把每个节点都当作潜在的顶点来访问。

复杂度： O(N)。

void inorder(TreeNode* root, vector<int>& arr) {
    if (!root) return;
    inorder(root->left, arr);
    arr.push_back(root->val);
    inorder(root->right, arr);
}

int findMedian(TreeNode* root) {
    vector<int> arr;
    inorder(root, arr);
    return arr[(arr.size() - 1) / 2];  // 偶数 N 时取下中位数
}

大树优化： 用题目 5.5.2 的第 K 小方法直接查找——无需展平：kthSmallest(root, (n+1)/2)，节省 O(N) 内存。

复杂度： O(N) 时间和空间（或用第 K 小方法 O(H + N/2)）。

核心思路： DFS 返回「从该节点向下出发的最优单侧路径」。全局答案考虑「以该节点为顶点的最优双侧路径」。负值子路径夹在 0 处（不包含它们）。

int bestSum = INT_MIN;
int maxGain(TreeNode* root) {
    if (!root) return 0;
    // 夹到 0：可以选择不包含子树（如果它是负的）
    int L = max(0, maxGain(root->left));
    int R = max(0, maxGain(root->right));

    // 以 root 为转折点的最优路径
    bestSum = max(bestSum, root->val + L + R);

    // 向父节点返回单侧路径（只能选一个分支）
    return root->val + max(L, R);
}
// 答案：调用 maxGain(root) 后的 bestSum

关键思路： 路径是「V」形——先上到某个顶点，再下来。每个节点恰好作为顶点考虑一次。

复杂度： O(N)。

思路： 后序 DFS，从叶节点向上累加。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<long long> val(n + 1);
    for (int i = 1; i <= n; i++) cin >> val[i];
    
    vector<vector<int>> children(n + 1);
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        children[p].push_back(i);
    }
    
    vector<long long> sub(n + 1);
    function<void(int)> dfs = [&](int u) {
        sub[u] = val[u];
        for (int v : children[u]) { dfs(v); sub[u] += sub[v]; }
    };
    dfs(1);
    
    for (int i = 1; i <= n; i++) cout << sub[i] << " \n"[i==n];
    return 0;
}

复杂度： O(N) 时间与空间。

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> adj[100005];

pair<int,int> bfs_far(int src) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    dist[src] = 0; q.push(src);
    int far = src;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
                if (dist[v] > dist[far]) far = v;
            }
        }
    }
    return {far, dist[far]};
}

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;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    auto [u, _] = bfs_far(1);
    auto [v, d] = bfs_far(u);
    cout << d << "\n";
    return 0;
}

直接使用 §5.5.8 的 LCA 二进制倍增实现：

// 见 §5.5.8 完整实现（dfs 预处理 + lca 查询函数）
// main() 中：
int n, q; cin >> n >> q;
// 读入树，dfs(1, 1, 0)，然后 q 次查询 lca(u, v)

追踪（树：1-2-3-4 链，查询 lca(4,1)）：

depth = [_, 0, 1, 2, 3]
anc[4][0]=3, anc[4][1]=1（3的父的父）, anc[3][0]=2, ...

lca(4, 1): depth[4]=3 > depth[1]=0
  diff=3=0b11, k=0时(diff>>0)&1=1, u=anc[4][0]=3
  k=1时(diff>>1)&1=1, u=anc[3][1]=1
  现在 depth[1]=depth[1]=0, u==v=1, 返回 1 ✓

思路： 构建欧拉序后，用前缀和数组 O(1) 回答每次查询。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN];
long long val[MAXN];
int in_t[MAXN], out_t[MAXN], timer_v = 0;
long long ea[MAXN];  // 欧拉序展平后的值数组

void dfs(int u, int par) {
    in_t[u] = ++timer_v;
    ea[timer_v] = val[u];
    for (int v : adj[u])
        if (v != par) dfs(v, u);
    out_t[u] = timer_v;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; cin >> n;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    cin >> q;
    
    dfs(1, -1);
    
    // 前缀和
    long long prefix[MAXN] = {};
    for (int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + ea[i];
    
    while (q--) {
        int u; cin >> u;
        cout << prefix[out_t[u]] - prefix[in_t[u]-1] << "\n";
    }
    return 0;
}

为什么正确？ 欧拉序保证 u 的子树节点恰好占据 [in_t[u], out_t[u]] 区间，前缀和 O(1) 回答区间和。

用 Kruskal 算法（并查集详见第 5.6 章）：

#include <bits/stdc++.h>
using namespace std;

vector<int> par, rnk;
int find(int x) { return par[x]==x ? x : par[x]=find(par[x]); }
bool unite(int x, int y) {
    x=find(x); y=find(y);
    if (x==y) return false;
    if (rnk[x]<rnk[y]) swap(x,y);
    par[y]=x; if(rnk[x]==rnk[y]) rnk[x]++;
    return true;
}

int main() {
    int n, m; cin >> n >> m;
    par.resize(n+1); rnk.assign(n+1,0);
    iota(par.begin(),par.end(),0);
    
    vector<tuple<int,int,int>> edges(m);
    for (auto& [w,u,v] : edges) cin >> u >> v >> w;
    sort(edges.begin(), edges.end());
    
    long long ans = 0; int cnt = 0;
    for (auto [w,u,v] : edges)
        if (unite(u,v)) { ans+=w; if(++cnt==n-1) break; }
    
    cout << (cnt==n-1 ? to_string(ans) : "IMPOSSIBLE") << "\n";
    return 0;
}