树的存储：父亲孩子表示法与孩子表示法

一句话算法

树有 $n$ 个点、$n-1$ 条边，每个点记下"孩子们是谁"，这 $n-1$ 条边就一条不漏地存住了；再顺手记一行"父亲是谁"，向上向下就都快了。

问题模型

给一棵有根树：$n$ 个点（编号 $1 \sim n$）、一个根 $root$、$n-1$ 条边。存储结构需要支持：

• 枚举点 $u$ 的所有孩子；
• 找到点 $u$ 的父亲；
• 遍历整棵树：自顶向下（从根往叶子）和自底向上（从叶子往根）。

目标是用 $O(n)$ 空间存下整棵树，并且让上面这些操作足够快。

核心直觉

树上每个点只有一个父亲，却可能有多个孩子，所以信息只有两个方向：向下找孩子和向上找父亲。

• 孩子表示法：每个点向下看，记"我的孩子都有谁"，一个孩子列表数组 ch[u] 就够。枚举孩子是 $O(\text{孩子数})$，但想向上找父亲，只能把所有孩子列表扫一遍。
• 父亲孩子表示法：在孩子表示法的基础上，每个点再记一行 fa[u]“我的父亲是谁”。多花一个数组，两个方向就都是 $O(1)$。

为什么这么少的信息就够？因为树只有 $n-1$ 条边，而且每条边连接的恰好是一个父亲和一个孩子。把每个点的孩子记一遍，$n-1$ 条边就全在了；而树中任意两点间的路径唯一，边存住了，整棵树的结构就存住了。

有的资料还单列"父亲表示法"（只记 fa[u] 不记孩子），它没法自顶向下遍历，用途有限，可以看作父亲孩子表示法的一半，本文不单独展开。如果每点最多两个孩子，就退化成二叉树，用 lch[u]、rch[u] 两个数组记录左右孩子即可；"左孩子右兄弟"表示法用 child[u] 和 sib[u] 两个数组存任意多叉树，本文也不展开。

算法步骤

一、父亲孩子表示法

1. 开数组 fa[1..n] 和列表数组 ch[1..n]，令 fa[root] = 0，表示根没有父亲。
2. 对每条父子边（$u$ 是父亲，$v$ 是孩子）：ch[u].push_back(v)，同时 fa[v] = u。
3. 查询：枚举 $u$ 的孩子就是扫描 ch[u]；找父亲直接读 fa[u]；向上跳祖先就是不断走 u = fa[u]。

二、孩子表示法

1. 开列表数组 ch[1..n]，初始都为空。
2. 对每条父子边（$u$ 是父亲，$v$ 是孩子）：ch[u].push_back(v)。
3. 查询：枚举 $u$ 的孩子就是扫描 ch[u]。不记 fa[]，向上找父亲要扫描所有列表，代价 $O(n)$。

三、从无向边输入建有根树

题目给的往往是 $n-1$ 条无向边（树是特殊的图，可以直接用图的存储里的邻接表先存下）。再从 $root$ 出发做一次 DFS 或 BFS 把方向定下来：

1. 从 $root$ 开始遍历，用 fa[] 同时兼任"已访问"标记，令 fa[root] = 0。
2. 从 $u$ 走到没访问过的邻居 $v$ 时，说明 $v$ 是 $u$ 的孩子：ch[u].push_back(v)，fa[v] = u。
3. 遍历结束时，父亲孩子表示法就建好了；不需要向上跳时，把 fa[] 省掉就是孩子表示法。

算法证明

需要证明的是：两种表示法都完整记录了树的全部边，不多也不少；无向边建表算法给出的父亲关系是正确的。

孩子表示法的不变量：ch[u] 中保存的恰好是 $u$ 的所有孩子，每个孩子出现一次。

每条边 $(u, v)$（$u$ 是父亲）恰好在 ch[u] 中出现一次；$n-1$ 条边一共被记录 $n-1$ 次，与树的边集一一对应，所以孩子列表可以完整恢复整棵树。

父亲孩子表示法的不变量：在上面的基础上，对每个非根点 $v$，fa[v] 恰好是树中 $v$ 到 $root$ 路径上的第二个点（即 $v$ 的父亲）。

1. 建表时每个非根点恰好写一次 fa[v]，对应一条边 $(v, fa[v])$。
2. 一共有 $n-1$ 个非根点，得到 $n-1$ 条边；这些边互不相同（每条边的"孩子端"就是下标 $v$）。

所以 fa[] 记录的边与树的边集也一一对应，两个方向互相印证。

DFS 建表的正确性：树中任意两点之间有且仅有一条简单路径。从 $root$ 出发遍历时，点 $v$ 第一次被走到的那条边，一定来自它到 $root$ 路径上的相邻点，也就是它的父亲；而之后从 $v$ 的孩子绕回来的"回头边"会被"是否等于 fa[u]"的判断挡掉。因此每个点恰好入表一次，记下的父子关系就是真实的父子关系。

复杂度分析

设点数为 $n$，边数为 $n-1$。

• 建表时间复杂度：$O(n)$，每个点、每条边恰好处理一次。
• 空间复杂度：$O(n)$。所有孩子列表一共只装 $n-1$ 个孩子；父亲孩子表示法多一个 fa[] 数组，还是 $O(n)$。

代码模板

父亲孩子表示法

全局数组 fa[]、ch[] 加两个函数，直接复制进程序就能用。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

        #include <cstring>
#include <vector>

// 树的存储：父亲孩子表示法
// 每个点记两个方向：fa[u] 是父亲，ch[u] 是孩子列表，向上向下都 O(1)。
// 孩子列表一共只装 n-1 个孩子，总空间 O(n)。
// 适用：树形 DP、DFS/BFS 遍历、换根这类两个方向都要的问题。
// 如何使用：
// 1. init(n);                // 多组数据必须调用
// 2. add_child(u, v);        // u 是 v 的父亲
// 3. 向下：for (int v : ch[u]) ... ；向上：fa[u]

const int maxn = 1e6 + 5;  // 和别的模板一起用时 maxn 只留一份

int fa[maxn];               // fa[u]：u 的父亲；fa[root] = 0，根没有父亲
std::vector<int> ch[maxn];  // ch[u]：u 的孩子，按加入顺序

// 初始化：把 1..n 清空，fa 全为 0（fa[root] = 0 正好表示"根没有父亲"）
void init(int n) {
    for (int i = 0; i <= n; i++) ch[i].clear();
    memset(fa, 0, sizeof(fa));
}

// u 是 v 的父亲：孩子挂到 ch[u]，父亲写进 fa[v]，加边 O(1)
void add_child(int u, int v) {
    ch[u].push_back(v);
    fa[v] = u;
}
    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

        # 树的存储：父亲孩子表示法
# 每个点记两个方向：fa[u] 是父亲，ch[u] 是孩子列表，向上向下都 O(1)。
# 孩子列表一共只装 n-1 个孩子，总空间 O(n)。
# 适用：树形 DP、DFS/BFS 遍历、换根这类两个方向都要的问题。
# 如何使用：
# 1. init(n)         # 多组数据必须调用
# 2. add_child(u, v) # u 是 v 的父亲
# 3. 向下：for v in ch[u] ... ；向上：fa[u]

fa: list[int] = []           # fa[u]：u 的父亲；fa[root] = 0，根没有父亲
ch: list[list[int]] = []     # ch[u]：u 的孩子，按加入顺序


def init(n: int) -> None:
    """把 1..n 清空，fa 全为 0（fa[root] = 0 正好表示"根没有父亲"）。"""
    global fa, ch
    fa = [0] * (n + 1)
    ch = [[] for _ in range(n + 1)]


def add_child(u: int, v: int) -> None:
    """u 是 v 的父亲：孩子挂到 ch[u]，父亲写进 fa[v]，加边 O(1)。"""
    ch[u].append(v)
    fa[v] = u
    

孩子表示法

只留 ch[]，不记父亲。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

        #include <vector>

// 树的存储：孩子表示法
// 每个点只记孩子列表 ch[u]，不记父亲；孩子一共 n-1 个，空间 O(n)。
// 只适合向下走：枚举孩子 O(孩子数)；想向上找父亲只能把所有列表扫一遍 O(n)。
// 适用：只自顶向下遍历或递推、从不回头的问题。
// 如何使用：
// 1. init(n);                // 多组数据必须调用
// 2. add_child(u, v);        // u 是 v 的父亲
// 3. 向下：for (int v : ch[u]) ...
// 要向上跳就改用父亲孩子表示法（tree_save_parent_child.cpp）。

const int maxn = 1e6 + 5;  // 和别的模板一起用时 maxn 只留一份

std::vector<int> ch[maxn];  // ch[u]：u 的孩子，按加入顺序

// 初始化：把 1..n 清空
void init(int n) {
    for (int i = 0; i <= n; i++) ch[i].clear();
}

// u 是 v 的父亲：孩子挂到 ch[u]，加边 O(1)
void add_child(int u, int v) {
    ch[u].push_back(v);
}
    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

        # 树的存储：孩子表示法
# 每个点只记孩子列表 ch[u]，不记父亲；孩子一共 n-1 个，空间 O(n)。
# 只适合向下走：枚举孩子 O(孩子数)；想向上找父亲只能把所有列表扫一遍 O(n)。
# 适用：只自顶向下遍历或递推、从不回头的问题。
# 如何使用：
# 1. init(n)         # 多组数据必须调用
# 2. add_child(u, v) # u 是 v 的父亲
# 3. 向下：for v in ch[u] ...
# 要向上跳就改用父亲孩子表示法（tree_save_parent_child.py）。

ch: list[list[int]] = []     # ch[u]：u 的孩子，按加入顺序


def init(n: int) -> None:
    """把 1..n 清空。"""
    global ch
    ch = [[] for _ in range(n + 1)]


def add_child(u: int, v: int) -> None:
    """u 是 v 的父亲：孩子挂到 ch[u]，加边 O(1)。"""
    ch[u].append(v)
    

代码实现

完整的建树程序：读入 $n-1$ 条无向边，从 root 出发定父子建出父亲孩子表示法，然后自顶向下沿 ch[] 求每个点的深度，自底向上沿 fa[] 累加子树大小。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

        // 完整实现：从无向边输入建一棵有根树，输出每个点的深度和子树大小
// 输入：
//   第一行 n root
//   接下来 n-1 行 u v（无向边）
// 输出：
//   第一行 depth[1..n]，第二行 size[1..n]
//
// 建的是父亲孩子表示法：fa[] 记父亲，ch[] 记孩子列表。
//   自顶向下沿 ch[] 求深度
//   自底向上沿 fa[] 累加子树大小
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 1e5 + 5;

int n, root;
vector<int> g[maxn];   // 第一步：树是特殊的图，先用邻接表存 n-1 条无向边
vector<int> ch[maxn];  // 孩子列表 ch[]
int fa[maxn];          // 父亲 fa[]，两者合起来是父亲孩子表示法
int depth[maxn];       // 深度：到根的路径上的边数
int sz[maxn];          // 子树大小：以 u 为根的子树里的点数

// 从 root 出发 DFS（用栈模拟），确定每个点的父亲和孩子，同时得到遍历顺序
void build() {
    vector<int> order;  // DFS 顺序：父亲一定排在孩子前面
    vector<int> stk = {root};
    fa[root] = 0;  // 根没有父亲
    depth[root] = 0;
    while (!stk.empty()) {
        int u = stk.back();
        stk.pop_back();
        order.push_back(u);
        for (int v : g[u]) {
            if (v == fa[u]) continue;  // 树上 u 只有父亲这一条"回头边"
            fa[v] = u;                 // 第一次走到 v 的点就是 v 的父亲
            ch[u].push_back(v);
            depth[v] = depth[u] + 1;
            stk.push_back(v);
        }
    }

    // 自底向上（沿 fa[]）：逆序遍历，把子树大小累加到父亲上
    for (int i = 1; i <= n; i++) sz[i] = 1;  // 先算上自己
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        if (u != root) sz[fa[u]] += sz[u];
    }
}

int main() {
    scanf("%d %d", &n, &root);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    build();

    printf("depth:");
    for (int i = 1; i <= n; i++) printf(" %d", depth[i]);
    printf("\nsize:");
    for (int i = 1; i <= n; i++) printf(" %d", sz[i]);
    printf("\n");
    return 0;
}
    

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

        # 完整实现：从无向边输入建一棵有根树，输出每个点的深度和子树大小
# 输入：
#   第一行 n root
#   接下来 n-1 行 u v（无向边）
# 输出：
#   第一行 depth[1..n]，第二行 size[1..n]
#
# 建的是父亲孩子表示法：fa[] 记父亲，ch[] 记孩子列表。
#   自顶向下沿 ch[] 求深度
#   自底向上沿 fa[] 累加子树大小

import sys

def main() -> None:
    it = iter(sys.stdin.read().split())
    n = int(next(it))
    root = int(next(it))

    # 第一步：树是特殊的图，先用邻接表存 n-1 条无向边
    g: list[list[int]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u = int(next(it))
        v = int(next(it))
        g[u].append(v)
        g[v].append(u)

    ch: list[list[int]] = [[] for _ in range(n + 1)]  # 孩子列表 ch[]
    fa: list[int] = [0] * (n + 1)                     # 父亲 fa[]，合起来是父亲孩子表示法
    depth: list[int] = [0] * (n + 1)                  # 深度：到根的路径上的边数
    sz: list[int] = [1] * (n + 1)                     # 子树大小，先算上自己

    # 从 root 出发 DFS（用栈模拟），确定每个点的父亲和孩子，同时得到遍历顺序
    order: list[int] = []  # DFS 顺序：父亲一定排在孩子前面
    stk = [root]
    fa[root] = 0  # 根没有父亲
    while stk:
        u = stk.pop()
        order.append(u)
        for v in g[u]:
            if v == fa[u]:  # 树上 u 只有父亲这一条"回头边"
                continue
            fa[v] = u       # 第一次走到 v 的点就是 v 的父亲
            ch[u].append(v)
            depth[v] = depth[u] + 1
            stk.append(v)

    # 自底向上（沿 fa[]）：逆序遍历，把子树大小累加到父亲上
    for u in reversed(order):
        if u != root:
            sz[fa[u]] += sz[u]

    print("depth:", *(depth[i] for i in range(1, n + 1)))
    print("size:", *(sz[i] for i in range(1, n + 1)))


if __name__ == "__main__":
    main()
    

测试用例

输入（6 个点，根为 1）：

6 1
1 2
1 3
2 4
2 5
3 6

树的结构：1 的孩子是 2、3；2 的孩子是 4、5；3 的孩子是 6。

手工走一遍算法：

1. 自顶向下求深度：depth[1] = 0，depth[2] = depth[3] = 1，depth[4] = depth[5] = depth[6] = 2。
2. 自底向上求子树大小：叶子 sz[4] = sz[5] = sz[6] = 1，sz[2] = 1 + 1 + 1 = 3，sz[3] = 1 + 1 = 2，sz[1] = 1 + 3 + 2 = 6。

输出：

depth: 0 1 1 2 2 2
size: 6 3 2 1 1 1

边界用例：$n = 1$ 时没有边，输入 1 1，输出 depth: 0 与 size: 1，此时 fa[] 全是 0、孩子列表全为空，不需要任何特判。

应用分类详解

孩子表示法和父亲孩子表示法没有优劣之分，差别只在"要不要回头"：只往下走的问题用孩子表示法，上下都要走的问题用父亲孩子表示法。

一、自顶向下遍历与树形 DP（孩子表示法）

典型模式： 每个点的答案由它和所有孩子的信息合并而成，处理完子树就不再回头。 识别信号： “子树内”“以 $u$ 为根的”"每个点选或不选"这类按子树划分的问题。 核心建模： 用 ch[u] 枚举孩子做转移，DFS 先算完子树再合并到父亲。

二、向上向下都要走（父亲孩子表示法）

典型模式： 状态既要从孩子合并上来，也要从父亲传下来，或者要在父亲链上跳。 识别信号： 换根、“到所有点的距离”"向上跳 $k$ 级祖先"这类问题。 核心建模： 向下用 ch[u]，向上用 fa[u]，两个方向都是 $O(1)$。

三、无向边输入建有根树（邻接表 + DFS 定父子）

典型模式： 输入是 $n-1$ 条无向边，但题目里的树是有根树（或要自己选根）。 识别信号： "给定一棵树"然后列 $n-1$ 行两个整数，却不告诉你谁是谁的父亲。 核心建模： 先用邻接表存无向边，再从根出发一次 DFS 同时得到 fa[] 和 ch[]。

经典例题

1. luogu-P1352 没有上司的舞会

每个点选或不选，且选了 $v$ 就不能选它的父亲。这是最标准的树形 DP：f[u][0/1] 表示 $u$ 不选/选时子树内的最大快乐指数，转移时枚举 ch[u] 把孩子的贡献合并上来。孩子表示法让"枚举所有孩子"这一步是 $O(\text{孩子数})$ 的，整题复杂度 $O(n)$。

2. luogu-P2015 二叉苹果树

在树上留 $q$ 条边使根到叶子的苹果数最大，是树上背包：每个点的孩子就是一组物品，容量是留下的边数。用孩子列表枚举 ch[u] 做分组背包即可，这里每个点最多两个孩子，也顺便展示了"孩子列表退化成左右儿子"的情形。

3. luogu-P1364 医院设置

求选哪个点使所有点的带权距离和最小，标准做法是换根 DP：第一遍自顶向下求出以 1 为根的答案，第二遍把答案从父亲"传"给每个孩子。向下传要枚举 ch[u]，向上传要知道 fa[u]，两个方向都要，用父亲孩子表示法。

4. luogu-P3379 【模板】最近公共祖先

倍增求 LCA 的第一步就是记录 fa[u] = up[u][0]，之后所有操作都是在父亲链上跳。它展示了 fa[] 这一半的价值：只要能向上跳，就能在 $O(\log n)$ 时间内回答祖先查询。

参考

• 本书相关章节：图的存储、倍增求 LCA、树的直径