树的遍历

树的遍历

例题

例题 - Subtree Queries
CSES - 普及/提高-
例题 - 请努力完成本题，再阅读以下内容。解答

题目简单翻译：

n个节点的s树，节点1为根，每个节点有一个值vv。 你的任务是处理以下的查询：

  1. 将节点ss的值改为xx
  2. 计算ss节点的子树中所有值的和

输入：

第一行是nn, qq（查询数），第二行是v1..vnv_1 .. v_n，每个节点的值，之后n−1n-1行是树的边。

最后qq行是查询，或者是"11 ss xx"，或者是"22 xx"。

输出：打印类型2的查询的答案。

树的遍历数组 (traversal array)

树上的不少问题，都可以通过遍历数组（tree traversal array）的方式，转化为数组上的区间问题来处理。

最常用的遍历数组是DFN遍历数组，就是用DFS遍历时首次到达的节点顺序组成的数组。在DFN序中，每个节点出现一次。如下图所示：

容易看到，在DFN遍历数组下，每棵子树在数组中是连续的区间。所以DFN遍历数组经常可以用来解子树相关的问题。DFN遍历数组长度为N（节点数）。

题解 - Subtree Queries

利用DFN遍历数组，问题就转化为单点更改数组中的值（查询1），以及区间求和（查询2），是线段树或者树状数组的基础应用。

下面是用线段树的解法：

Subtree Queries题解代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, Q;
int v[200005];
vector<int> adj[200005];
int st[200005], en[200005]; // start and end of each subtree
ll tree[400005];
 
void set(int k, ll x) { 
    k += n;
    tree[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = tree[2*k]+tree[2*k+1];
    }
}
 
ll sum(int a, int b) { 
    a += n; b += n;
    ll s = 0;
    while (a <= b) {
        if (a%2 == 1) s += tree[a++];
        if (b%2 == 0) s += tree[b--];
        a /= 2; b /= 2;
    }
    return s;
}
 
int ti;
void dfs(int s, int e) {
    st[s] = ti++;
    for (int u: adj[s]) {
        if (u == e) continue;
        dfs(u, s);
    }
    en[s] = ti-1;
}
 
int main() {
    scanf("%d %d", &n, &Q);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    for (int i = 0; i < n-1; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0,-1);
    for (int i = 0; i < n; i++)
        set(st[i], v[i]);
 
    for (int i = 0; i < Q; i++) {
        int c,a,b;
        // queries
        scanf("%d %d", &c, &a);
        a--;
        if (c == 1) {
            scanf("%d", &b);
            set(st[a], b);
        } else {
            printf("%lld\n", sum(st[a], en[a]));
        }
    }
 
    return 0;
}

欧拉回路

另外一种遍历数组是欧拉回路(Euler tour)遍历数组，在DFS的每一步，包括初次访问，去下一节点前，以及再次回到此节点时，都记录一次访问。如下图所示。

欧拉回路遍历数组长度为2N-1.

欧拉回路可以用来求LCA，如上图，两个节点间的区间中，深度最小的点，就是这两个节点的LCA。

相关章节

树上DP与树上遍历密切相关，可以对照来练习。

习题

习题
P5658CSP-S括号树2019普及+/提高
T241758小图灵树上两点间距离之和普及+/提高
P6098USACO GoldCow Land2019提高+/省选-解答
P3605USACO PlatPromotion Counting2017提高+/省选-解答