树的边染色查询问题：Euler 序 + 双线段树 O(log N) 解法（cp-algorithms）

给定一棵包含 $N$ 个顶点的树，我们面临两类查询：一类是给某条边染色（或取消染色），另一类是查询任意两个顶点 $i$、$j$ 之间的路径上共有多少条边已被染色。这是竞赛中相当常见的一类"树上的路径统计 + 单点修改"问题。本文介绍 cp-algorithms 仓库中 tree_painting.md 提供的经典解法：利用 DFS 的 Euler 序配合两棵求和线段树，使每条查询在 $O(\log N)$ 时间内完成，预处理总代价为 $O(N)$。

读完本文，你将掌握一套可直接套用的技术：如何把"任意两点路径统计"拆成"祖先-后代对"的路径统计（借助 LCA）、如何用 Euler 序把树上路径转化为数组区间，以及如何用"正向边表与反向边表的差值"巧妙去除多余贡献，最终得到一份包含 LCA 计算在内的完整可运行 C++ 实现。

问题定义

• 输入：一棵有 $N$ 个顶点的树，边从 $0$ 到 $N-2$ 编号。
• 第一类查询（修改）：给某条边染色，或取消其染色。
• 第二类查询（询问）：统计顶点 $i$ 与顶点 $j$ 之间唯一简单路径上已被染色的边的条数。

朴素做法对每次询问沿路径逐边扫描是 $O(N)$ 的；若用 LCA + 树上前缀差分统计"永久染色"的边数可行，但这里染色状态是动态修改的，因此需要支持单点更新与区间求和的数据结构，也就是线段树。

核心思路：把路径查询降维成祖先-后代查询

设 $l = \mathrm{LCA}(i, j)$。由于树上 $i$、$j$ 之间只有一条简单路径，且该路径等于 $i$ 到 $l$ 的路径与 $j$ 到 $l$ 的路径的并集，所以第二类查询 $(i, j)$ 可以拆成两个子查询：

$$(i, j) \ \Rightarrow\ (l, i) + (l, j)$$

答案即为两个子查询结果之和。这两个子查询具有特殊结构：第一个顶点 $l$ 是第二个顶点的祖先。全文后续只需讨论这种"祖先-后代"形态的查询即可。LCA 本身可借助 Euler 序 + 线段树（或稀疏表等）在 $O(\log N)$ / $O(1)$ 内求出，详见仓库中的 lca.md。

预处理：Euler 序与双向边表

对以根为起点的树执行一次 DFS，并记录 Euler 序 dfs_list：每个顶点在首次访问时入表，并且在从每个子节点返回后再次入表。这与 LCA 预处理使用的 Euler 序技术完全相同，序列长度为 $O(N)$。

关键观察：每条边在这个序列中恰好出现两次，且两次出现时边的两个端点相邻：

• 正向出现：从较靠近根的一端 $i$ 走向较远离根的一端 $j$；
• 反向出现：从 $j$ 回到 $i$。

利用这一点，预处理时构建两个平行数组，并各建一棵求和线段树：

• tree1（$T1$）：覆盖所有边在 正向方向 上的出现位置，值为 $1$ 表示该边已染色，否则为 $0$；
• tree2（$T2$）：覆盖所有边在 反向方向 上的出现位置，值与 tree1 同步（染色时两处同时置 $1$）。

两棵树都支持"单点修改 + 区间求和"。线段树的原理、构建与查询细节可对照仓库中的 segment_tree.md。

为什么答案等于 T1 区间和减 T2 区间和

考虑祖先-后代查询 $(i, j)$（$i$ 是 $j$ 的祖先）。预处理时我们已经记录了每个顶点在 dfs_list 中的首次出现位置，因此可以在 $O(1)$ 内得到 $i$、$j$ 的位置 $p$、$q$（$p < q$）。答案公式为：

$$\mathrm{answer}(i, j) = T1[p \ldots q-1] - T2[p \ldots q-1]$$

为什么成立？考察 Euler 序中的区间 $[p, q]$：

• 它确实包含了 $i$ 到 $j$ 路径上的全部边；
• 但它同时包含了从 $i$ 出发、进入其他子树后又返回的若干"绕行"边。

两类边的关键差异在于出现次数：

• 路径上真正需要的边：只在正向方向出现一次（进入 $j$ 所在子树后不再返回 $i$ 方向的那一侧），反向位置不在区间内或贡献被抵消；
• 绕行的多余边：完整出现两次——正向一次、反向一次，因此 $T1$ 与 $T2$ 中都会计入该边。

于是 $T1[p \ldots q-1] - T2[p \ldots q-1]$ 中，多余边因"正一次反一次"而被恰好抵消，只剩路径上真正被染色的边。区间右端取 $q-1$ 而非 $q$，是为了避免多捕获一条从顶点 $j$ 出发的额外边。线段树的区间求和复杂度为 $O(\log N)$。

修改（第一类查询）：染色/取消染色某条边

染色操作比询问更简单：只需对 tree1 与 tree2 中对应这条边的那两个位置各做一次单点更新。

预处理时我们为每条边记录：

• first1[x]：边 $x$ 在 edges_list 中正向出现的位置；
• first2[x]：边 $x$ 在 edges_list 中反向出现的位置；

二者都可在预处理阶段 $O(1)$ 求出来。染色（start = true）时在两棵树中对该位置加 $1$，取消染色（start = false）时加 $-1$。线段树的单点修改同样是 $O(\log N)$。

完整实现（含 LCA 计算）

下面是仓库文档中的完整 C++ 实现。它把"树的 DFS + Euler 序"、"基于线段树的 LCA"、"边向量的双向位置索引"以及"两棵求和线段树"整合在一起：

const int INF = 1000 * 1000 * 1000;

typedef vector<vector<int>> graph;

vector<int> dfs_list;
vector<int> edges_list;
vector<int> h;

void dfs(int v, const graph& g, const graph& edge_ids, int cur_h = 1) {
    h[v] = cur_h;
    dfs_list.push_back(v);
    for (size_t i = 0; i < g[v].size(); ++i) {
        if (h[g[v][i]] == -1) {
            edges_list.push_back(edge_ids[v][i]);
            dfs(g[v][i], g, edge_ids, cur_h + 1);
            edges_list.push_back(edge_ids[v][i]);
            dfs_list.push_back(v);
        }
    }
}

vector<int> lca_tree;
vector<int> first;

void lca_tree_build(int i, int l, int r) {
    if (l == r) {
        lca_tree[i] = dfs_list[l];
    } else {
        int m = (l + r) >> 1;
        lca_tree_build(i + i, l, m);
        lca_tree_build(i + i + 1, m + 1, r);
        int lt = lca_tree[i + i], rt = lca_tree[i + i + 1];
        lca_tree[i] = h[lt] < h[rt] ? lt : rt;
    }
}

void lca_prepare(int n) {
    lca_tree.assign(dfs_list.size() * 8, -1);
    lca_tree_build(1, 0, (int)dfs_list.size() - 1);

    first.assign(n, -1);
    for (int i = 0; i < (int)dfs_list.size(); ++i) {
        int v = dfs_list[i];
        if (first[v] == -1)
            first[v] = i;
    }
}

int lca_tree_query(int i, int tl, int tr, int l, int r) {
    if (tl == l && tr == r)
        return lca_tree[i];
    int m = (tl + tr) >> 1;
    if (r <= m)
        return lca_tree_query(i + i, tl, m, l, r);
    if (l > m)
        return lca_tree_query(i + i + 1, m + 1, tr, l, r);
    int lt = lca_tree_query(i + i, tl, m, l, m);
    int rt = lca_tree_query(i + i + 1, m + 1, tr, m + 1, r);
    return h[lt] < h[rt] ? lt : rt;
}

int lca(int a, int b) {
    if (first[a] > first[b])
        swap(a, b);
    return lca_tree_query(1, 0, (int)dfs_list.size() - 1, first[a], first[b]);
}

vector<int> first1, first2;
vector<char> edge_used;
vector<int> tree1, tree2;

void query_prepare(int n) {
    first1.resize(n - 1, -1);
    first2.resize(n - 1, -1);
    for (int i = 0; i < (int)edges_list.size(); ++i) {
        int j = edges_list[i];
        if (first1[j] == -1)
            first1[j] = i;
        else
            first2[j] = i;
    }

    edge_used.resize(n - 1);
    tree1.resize(edges_list.size() * 8);
    tree2.resize(edges_list.size() * 8);
}

void sum_tree_update(vector<int>& tree, int i, int l, int r, int j, int delta) {
    tree[i] += delta;
    if (l < r) {
        int m = (l + r) >> 1;
        if (j <= m)
            sum_tree_update(tree, i + i, l, m, j, delta);
        else
            sum_tree_update(tree, i + i + 1, m + 1, r, j, delta);
    }
}

int sum_tree_query(const vector<int>& tree, int i, int tl, int tr, int l, int r) {
    if (l > r || tl > tr)
        return 0;
    if (tl == l && tr == r)
        return tree[i];
    int m = (tl + tr) >> 1;
    if (r <= m)
        return sum_tree_query(tree, i + i, tl, m, l, r);
    if (l > m)
        return sum_tree_query(tree, i + i + 1, m + 1, tr, l, r);
    return sum_tree_query(tree, i + i, tl, m, l, m) +
           sum_tree_query(tree, i + i + 1, m + 1, tr, m + 1, r);
}

int query(int v1, int v2) {
    return sum_tree_query(tree1, 1, 0, (int)edges_list.size() - 1, first[v1], first[v2] - 1) -
           sum_tree_query(tree2, 1, 0, (int)edges_list.size() - 1, first[v1], first[v2] - 1);
}

int main() {
    // reading the graph
    int n;
    scanf("%d", &n);
    graph g(n), edge_ids(n);
    for (int i = 0; i < n - 1; ++i) {
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        --v1, --v2;
        g[v1].push_back(v2);
        g[v2].push_back(v1);
        edge_ids[v1].push_back(i);
        edge_ids[v2].push_back(i);
    }

    h.assign(n, -1);
    dfs(0, g, edge_ids);
    lca_prepare(n);
    query_prepare(n);

    for (;;) {
        if () {
            // request for painting edge x;
            // if start = true, then the edge is painted, otherwise the painting
            // is removed
            edge_used[x] = start;
            sum_tree_update(tree1, 1, 0, (int)edges_list.size() - 1, first1[x],
                            start ? 1 : -1);
            sum_tree_update(tree2, 1, 0, (int)edges_list.size() - 1, first2[x],
                            start ? 1 : -1);
        } else {
            // query the number of colored edges on the path between v1 and v2
            int l = lca(v1, v2);
            int result = query(l, v1) + query(l, v2);
            // result - the answer to the request
        }
    }
}

关键函数逐一解读

函数	作用	复杂度
dfs(v, g, edge_ids, cur_h)	从根出发生成 dfs_list（顶点 Euler 序）与 edges_list（边双向出现序列），同时记录高度 h	$O(N)$
lca_prepare(n) / lca_tree_build	在 dfs_list 上建一棵"存深度最小顶点"的线段树，并记录每个顶点首次出现位置 first	$O(N)$
lca(a, b) / lca_tree_query	用 RMQ 思想在区间 first[a]..first[b] 上找高度最小的顶点，即 LCA	$O(\log N)$
query_prepare(n)	扫描 edges_list，为每条边记录正向位置 first1 与反向位置 first2，并分配两棵线段树数组	$O(N)$
sum_tree_update	求和线段树单点加 delta	$O(\log N)$
sum_tree_query	求和线段树区间查询	$O(\log N)$
query(v1, v2)	计算 T1 - T2 在区间 first[v1]..first[v2]-1 上的差值，即祖先-后代路径上的染色边数	$O(\log N)$

几个实现细节值得注意：

• query(v1, v2) 要求 v1 是 v2 的祖先；主循环中通过 l = lca(v1, v2) 后分别调用 query(l, v1) 与 query(l, v2) 来回答任意顶点对。
• 线段树数组按 size * 8 分配，保证最坏情况（Euler 序长度超过 $2N$ 的极端形态）下标不越界；这也是 segment_tree.md 中所述"线性内存、$O(\log N)$ 高度"性质在该场景下的直接应用。
• 边编号通过 edge_ids 与顶点邻接表一一对应，染色时通过 first1[x]、first2[x] 定位边 $x$ 在 edges_list 中的两处位置，做到 $O(1)$ 定位。
• edge_used 数组记录了当前染色状态，用于保证对同一位置重复施加 +1/-1 不会产生累计偏差。

复杂度总结

• 预处理：一次 DFS 生成 Euler 序（$O(N)$）+ 建立 LCA 线段树（$O(N)$）+ 建立两棵求和线段树（$O(N)$），总计 $O(N)$ 时间与 $O(N)$ 内存。
• 第一类查询（染色/取消染色）：两棵线段树各一次单点更新，$O(\log N)$。
• 第二类查询（路径染色边数）：LCA 一次 $O(\log N)$ + 两个子查询各 $O(\log N)$，合计 $O(\log N)$。

在仓库中的位置与扩展阅读

• 本文的原始出处为 src/graph/tree_painting.md，该文档位于 Graph 模块的 "Miscellaneous" 分组中（见 src/navigation.md）。
• 依赖的两大基础组件：求和线段树 src/data_structures/segment_tree.md，以及 Euler 序 + RMQ 求 LCA 的完整说明与另一份实现 src/graph/lca.md。
• DFS 与 Euler 序的通用介绍见 src/graph/depth-first-search.md。

这套"Euler 序 + 双向边表 + 两棵线段树相减"的思路，本质上是把树上路径统计转化为数组区间统计，与 Heavy-Light 分解（见 src/graph/hld.md）殊途同归：后者通过把树剖分成若干重路径把路径查询拆成 $O(\log N)$ 个区间查询，而本文的方案借助"多余边正反各出现一次被抵消"这一巧妙性质，实现了更轻量的常数与更短的实现代码。当树形态给定且只需处理边染色这种单点修改时，这是一个非常实用的选择。