vector 存树 · 遍历 · 子树大小

从“一堆边”变成“每个点一个列表”，再用 DFS 把它走一遍

邻接表 = 每个点一个 vector 树只有 N−1 条边，别开 N×N DFS 必须跳过父亲 size 是后序回溯累加

换一棵树试试：

①存图：把边搬进 vector

输入给你 N−1 条边。我们不记"边"，而是记"每个点跟谁相邻"——这就是邻接表。

开一个 vector<int> g[N]，g[u] 里放所有和 u 直接相连的点。每读一条边 (u, v)，做两件事：

for (int i = 1; i < n; i++) {    int u, v;  cin >> u >> v;    g[u].push_back(v);   // u 的邻居里加一个 v    g[v].push_back(u);   // v 的邻居里加一个 u（无向边）}

为什么加两次：边是没有方向的，从 u 能走到 v，从 v 也能走到 u。只加一次的话，反着走就断了。

写法为什么顺：g[u] 就是 u 的邻居清单，遍历时直接 for (int v : g[u])，既不用问“这条边存不存在”，也不用判断“这个格子是不是 0”。下一节专门算一笔账：为什么这件事不能交给二维数组。

二维数组也能存图，可是对一棵只有 N−1 条边的树来说，它把绝大部分空间花在“这里没有边”上。

矩阵的写法是开一个 int a[N][N]，a[u][v] = 1 表示 u 和 v 之间有边。它必须开满 N 行 N 列，而树里真正有边的格子只有 2(N−1) 个。

点数 N = 1000　（拖动滑块看代价怎么变）

int a[N][N]

—

vector<int> g[N]

—

—

矩阵 = N × N × 4 字节，非零格子只占 2(N−1) 个

—

邻接表 = 正好 2(N−1) 个 int，一个不多

—

矩阵：每个点都得扫一整行 N 格

—

邻接表：所有 g[u] 加起来恰好 2(N−1)

—

判据（记这一条就够）：设边数为 M。M 远小于 N² —— 树、稀疏图 —— 用 vector；M 接近 N²（稠密图）、或要反复 O(1) 查边、或跑 Floyd 最短路，才轮到矩阵。树的 M 恒等于 N−1，所以矩阵在任何一档 N 上都亏。

一句话比喻：矩阵是给每个人发一张“全校点名表”，上面 99% 的格子写着“不认识”；邻接表是每人只拿自己的好友名单。树里所有人的好友名单加起来，只有 2N−2 个名字。

从根 1 出发，每次挑一个还没走过的邻居走下去，走不动了就退回上一个点。这就是 DFS（深度优先搜索）。

—

为什么必须写 if (v == fa) continue;：vector 里存的是无向邻居，父亲也在里面。不跳过它，你就会从儿子走回父亲，来回死循环。

同样用 DFS，只是顺序反过来想：我先不知道自己的大小，得先问所有儿子；儿子都报完了，我再把它们加起来。

—

一句话记住：进入时先记 sz[u] = 1（算自己），等儿子 dfs(v,u) 返回后，再 sz[u] += sz[v]。写在递归调用之后，就是"后序"。

坑	后果 / 正确做法
无向边只加了一次	反方向走不通，遍历会漏点。必须 `g[u].push_back(v)` 和 `g[v].push_back(u)` 各一次。
忘了跳过父亲	u → 父亲 → u → 父亲…… 无限递归，直接爆栈。传一个 `fa` 参数，或开 `vis` 数组。
链状树递归太深	N = 2×10⁵ 的链，递归 20 万层会栈溢出。需要用能控制深度的写法（后面单独讲）。
多组数据不清空	上一组残留的邻居还在 g 里。每组开始 `for (int i = 1; i <= n; i++) g[i].clear();`

关于递归深度：链状树 N = 2×10⁵ 时，递归 20 万层会把系统栈撑爆。这件事有专门的迭代写法（自己开一个栈），放到后面的课再讲。现在只需记住一条：看到“链”加上“2×10⁵”，就别直接交递归。