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

const int MAXN = 100001;
vector<int> adj[MAXN];
int in_time[MAXN], out_time[MAXN];
int order[MAXN];       // order[i] = 第 i 个被访问的顶点
int timer_val = 0;

void dfs(int u, int par) {
    in_time[u] = ++timer_val;   // 记录进入时刻
    order[timer_val] = u;        // 记录该位置对应的顶点

    for (int v : adj[u]) {
        if (v != par)
            dfs(v, u);
    }

    out_time[u] = timer_val;    // 记录退出时刻（等于或晚于 in_time）
}

树（以 1 为根）：         DFS 顺序：          进/出时刻：
       1                 访问 1             in[1]=1, out[1]=7
      /|\                访问 2             in[2]=2, out[2]=4
     2  5  7             访问 4             in[4]=3, out[4]=3
    /|   \               返回 2             
   4  3   6              访问 3             in[3]=4, out[3]=4
                         返回 1             
                         访问 5             in[5]=5, out[5]=6
                         访问 6             in[6]=6, out[6]=6
                         返回 1             
                         访问 7             in[7]=7, out[7]=7

顶点 2 的子树 = {2, 4, 3} → 区间 [2, 4]  ✓ (in[2]=2, out[2]=4)
顶点 5 的子树 = {5, 6}    → 区间 [5, 6]  ✓ (in[5]=5, out[5]=6)
顶点 1 的子树 = 全部       → 区间 [1, 7]  ✓ (in[1]=1, out[1]=7)

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

const int MAXN = 100001;
vector<int> adj[MAXN];
int in_time[MAXN], out_time[MAXN];
int val[MAXN];       // 顶点值
int flat[MAXN];      // flat[i] = 欧拉游览第 i 个位置对应顶点的值
int timer_val = 0;

// ── 树状数组（BIT），支持区间求和 ─────────────────
long long bit[MAXN];
int n;

void bit_update(int i, long long delta) {
    for (; i <= n; i += i & (-i))
        bit[i] += delta;
}

long long bit_query(int i) {
    long long s = 0;
    for (; i > 0; i -= i & (-i))
        s += bit[i];
    return s;
}

long long bit_range(int l, int r) {
    return bit_query(r) - bit_query(l - 1);
}

// ── 欧拉游览 DFS ────────────────────────────────────
void dfs(int u, int par) {
    in_time[u] = ++timer_val;
    flat[timer_val] = val[u];        // 将顶点值放到游览对应位置

    for (int v : adj[u]) {
        if (v != par) dfs(v, u);
    }

    out_time[u] = timer_val;
}

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

    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);
    }

    dfs(1, 0);

    // 用 flat 数组初始化 BIT
    for (int i = 1; i <= n; i++)
        bit_update(i, flat[i]);

    // 查询示例：
    // 顶点 v 的子树和：
    int v;
    cin >> v;
    cout << bit_range(in_time[v], out_time[v]) << "\n";

    // 将顶点 u 的值增加 delta：
    int u; long long delta;
    cin >> u >> delta;
    bit_update(in_time[u], delta);

    return 0;
}

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

const int MAXN = 100001;
const int LOG = 17;  // 2^17 > 10^5

vector<int> adj[MAXN];
int up[MAXN][LOG];   // up[v][k] = v 的第 2^k 个祖先
int depth[MAXN];

void dfs(int u, int par, int d) {
    depth[u] = d;
    up[u][0] = par;  // 直接父节点

    // 填充倍增表
    for (int k = 1; k < LOG; k++) {
        up[u][k] = up[up[u][k-1]][k-1];
        // 第 2^k 个祖先 = 第 2^(k-1) 个祖先的第 2^(k-1) 个祖先
    }

    for (int v : adj[u]) {
        if (v != par)
            dfs(v, u, d + 1);
    }
}

// 求 u 和 v 的 LCA
int lca(int u, int v) {
    // 第 1 步：将 u 和 v 提升到同一深度
    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)   // 若 diff 的第 k 位为 1
            u = up[u][k];      // 向上跳 2^k 步
    }

    // 现在 depth[u] == depth[v]
    if (u == v) return u;      // u 在 v 的子树中（或反之）

    // 第 2 步：同时对 u 和 v 二分倍增，找 LCA
    for (int k = LOG - 1; k >= 0; k--) {
        if (up[u][k] != up[v][k]) {  // 若祖先不同则向上跳
            u = up[u][k];
            v = up[v][k];
        }
    }

    return up[u][0];  // 当前位置再往上一步 = 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);
    }

    // 初始化：根 = 1，根的父节点指向自身（哨兵）
    up[1][0] = 1;
    dfs(1, 1, 0);

    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }

    return 0;
}

重子节点：子树最大的子节点
重路径：从某顶点沿重子节点向下到叶节点的链

树：            sz[] 值：       重边（→）：
    1  (sz=7)      7
   / \            / \
  2   3 (sz=4)   3   4
 / \ / \        / \ / \
4  5 6  7      1 1 2  1

重子节点：1→3 (sz=4 > sz=3), 3→6 (sz=2 > sz=1)
重链：{1, 3, 6}、{2}、{4}、{5}、{7}

// 重链剖分 — O(N log N) 预处理，O(log²N) 路径查询
// 完整实现是 Platinum 级别；以下是概念性草图

int heavy[MAXN];   // heavy[v] = v 的重子节点（叶节点为 -1）
int head[MAXN];    // head[v] = v 所在重链的顶端节点
int pos[MAXN];     // pos[v] = v 在 HLD 展开数组中的位置
int cur_pos = 0;

// 第 1 步：找重子节点（需先用树形 DP 计算 sz[]）
void find_heavy(int u, int par) {
    sz[u] = 1;
    heavy[u] = -1;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        find_heavy(v, u);
        sz[u] += sz[v];
        if (sz[v] > max_sz) {
            max_sz = sz[v];
            heavy[u] = v;   // v 是重子节点
        }
    }
}

// 第 2 步：沿重链分配位置
void decompose(int u, int par, int h) {
    head[u] = h;            // 链头
    pos[u] = cur_pos++;     // 在展开数组中的位置

    if (heavy[u] != -1)
        decompose(heavy[u], u, h);      // 延续重链

    for (int v : adj[u]) {
        if (v == par || v == heavy[u]) continue;
        decompose(v, u, v);             // 从 v 开始新链
    }
}

// 第 3 步：利用 LCA + 链跳转进行路径查询
long long path_query(int u, int v) {
    long long result = 0;
    while (head[u] != head[v]) {
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        // u 的链头更深；查询 pos[head[u]]..pos[u]
        result += seg_query(pos[head[u]], pos[u]);
        u = parent[head[u]];  // 跳到链头的父节点
    }
    // 现在 u 和 v 在同一条链上
    if (depth[u] > depth[v]) swap(u, v);
    result += seg_query(pos[u], pos[v]);  // 查询链上该段
    return result;
}

计算欧拉游览（进/出时刻）。对 DFS 序建立前缀和数组。查询为 prefix[out[v]] - prefix[in[v] - 1]，复杂度 O(N + Q)。

使用 8.4.3 节的倍增模板。O(N log N) 预处理，每次查询 O(log N)。

dist(u, v) = depth[u] + depth[v] - 2 * depth[LCA(u, v)]。用倍增求 LCA。

欧拉游览将 v 的子树映射为区间 [in[v], out[v]]。使用差分 BIT：O(log N) 区间更新，O(log N) 单点查询。

LCA + 欧拉游览路径和。对于动态更新，用以 DFS 序为下标的 BIT 维护前缀和。path_sum(u, v) = bit_prefix(in[u]) + bit_prefix(in[v]) - bit_prefix(in[lca]) - bit_prefix(in[parent(lca)])。

对固定的 v，路径 (u, w) 经过 v 当且仅当 LCA(u, w) = v，或 LCA(u, v) = v，或 LCA(v, w) = v。使用欧拉游览 + 计数：v 的答案等于 C(sz[v], 2) 减去完全在 v 某棵子树内的路径数。这需要对 v 各子节点的子树大小进行仔细的容斥。