核心逻辑与数学原理
树形结构本质上是由 $N$ 个节点和 $N-1$ 条边构成的连通无向图。在计算机内存中，非稠密树的存储标准方案为链式前向星或邻接表（动态数组）。由于树的拓扑结构不具备线性的连续内存特征，无法直接利用线段树、树状数组等高级数据结构进行区间维护，因此必须通过遍历技术将其“拍平”为线性序列。
1. DFS 序
DFS 序是指在对树进行深度优先遍历时，节点被首次访问的时间戳顺序。对于任意节点 $u$，其入栈时间戳记为 $ ext{dfn}[u]$，其子树中最后一个被访问节点的入栈时间戳记为 $ ext{out}[u]$。
数学性质：节点 $u$ 的整棵子树在 DFS 序中对应一个连续的闭区间 $[ ext{dfn}[u], ext{out}[u]]$。区间长度即为子树大小 $ ext{siz}[u] = ext{out}[u] - ext{dfn}[u] + 1$。这一性质建立了“树上子树操作”向“线段树区间操作”的同构映射。
2. 欧拉序
欧拉序有两种变体，NOIP 阶段特指“路径欧拉序”，即在 DFS 过程中，无论是首次进入节点还是从子树回溯，只要移动到该节点，就将其记录进序列。对于无根树，一条边会被正反遍历两次，总序列长度严格为 $2N-1$。
数学性质：节点 $u$ 首次出现位置为 $ ext{first}[u]$，最后一次出现位置为 $ ext{last}[u]$。区间 $[ ext{first}[u], ext{last}[u]]$ 包含了且仅包含了 $u$ 及其所有子树节点的所有遍历轨迹。路径欧拉序常用于配合常规 ST 表，将最近公共祖先（LCA）问题转化为区间最值问题（RMQ）。
算法推导与状态设计
定义树的拓扑结构 $G = (V, E)$。
1. 邻接表存图
使用 std::vector<int> G[N] 或 int head[N], to[M], nxt[M]。NOIP 工业标准推荐在非极端卡常题中采用 std::vector。对于带权树，状态结构体定义为：
struct Edge {
int to;
long long weight;
};
std::vector<Edge> adj[N];2. DFS 序转化方程
定义全局时间戳计数器 $ ext{tim}$。对于当前节点 $u$，双向边回溯父节点为 $fa$：
- 准入状态：$ ext{tim} ightarrow ext{tim} + 1$，令 $ ext{dfn}[u] = ext{tim}$，并将当前节点映射回序列 $ ext{seq}[ ext{tim}] = u$。
- 状态转移：遍历所有满足 $v ext{ in } ext{adj}[u] ext{ and } v eq fa$ 的子节点，递归执行 $ ext{DFS}(v, u)$。
- 退出状态：$ ext{out}[u] = ext{tim}$。
3. 欧拉序转化方程
定义全局时间戳计数器 $ ext{cur}$。
- 准入状态：$ ext{cur} ightarrow ext{cur} + 1$，令 $ ext{euler}[ ext{cur}] = u$，记录首次位置 $ ext{first}[u] = ext{cur}$。
- 状态转移：遍历子节点 $v$。每次从 $v$ 回溯到 $u$ 时，必须显式触发：$ ext{cur} ightarrow ext{cur} + 1$，令 $ ext{euler}[ ext{cur}] = u$。
- 退出状态：记录最终位置 $ ext{last}[u] = ext{cur}$。
C++ 标准源码
#include <iostream>
#include <vector>
#include <algorithm>
// 严格限定最大节点数，根据题目数据范围调整
const int MAXN = 200005;
// 邻接表存储结构
std::vector<int> adj[MAXN];
// DFS 序相关数组
int dfn[MAXN], out[MAXN], seq[MAXN], dfn_tim;
// 欧拉序相关数组
int euler[MAXN * 2], first_pos[MAXN], last_pos[MAXN], euler_tim;
// 核心遍历函数
void dfs(int u, int fa) {
// 激活 DFS 序
dfn_tim++;
dfn[u] = dfn_tim;
seq[dfn_tim] = u;
// Plan A: 记录首次进入欧拉序
euler_tim++;
euler[euler_tim] = u;
first_pos[u] = euler_tim;
for (size_t i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i];
if (v == fa) continue; // 致命死循环规避：无向图必须跳过父节点
dfs(v, u);
// Plan B: 从子树回溯，必须重复压入当前节点 u
euler_tim++;
euler[euler_tim] = u;
}
// 封闭 DFS 序子树区间
out[u] = dfn_tim;
last_pos[u] = euler_tim;
}
int main() {
// 提升 I/O 效率，解绑标准流
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
if (!(std::cin >> n)) return 0;
for (int i = 1; i < n; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u); // 无向树必须双向建边
}
// 初始化计数器并从根节点 1 开始 DFS
dfn_tim = 0;
euler_tim = 0;
dfs(1, 0);
// 输出验证结果（生产环境可删除）
for (int i = 1; i <= n; ++i) {
std::cout << "Node " << i << " Subtree Interval: [" << dfn[i] << ", " << out[i] << "]\n";
}
return 0;
}NOIP 实战避坑指南
- 爆栈（Stack Overflow）风险： 树深度过大（例如链状图，$N = 5 \times 10^5$）时，系统默认栈空间极易崩塌。在 Linux 评测环境下，必须注意系统栈限制。若无特殊编译命令，可考虑使用手工栈模拟 DFS。
- 欧拉序数组大小未翻倍：
回溯导致的重复入队使欧拉序列最大长度逼近 $2N$。若
euler数组及相关统计数组仅开辟MAXN大小，在数据为随机树或高扇出树时必然触发越界，造成SIGSEGV段错误。 - 无向边双向建边漏判父节点：
在
for循环遍历邻接表时，若不加if (v == fa) continue;判定，会导致在父子节点间无休止递归，直接引发死循环并爆栈。
经典 NOIP/洛谷 真题
1. 洛谷 P3384 【模板】重链剖分/树链剖分
- 题意描述： 已知一棵包含 $N$ 个节点的树，每个节点有初始权值。需要实现四种操作：修改节点 $X$ 到 $Y$ 路径上所有节点的权值；求节点 $X$ 到 $Y$ 路径上所有节点的权值和；修改以 $X$ 为根的子树内所有节点的权值；求以 $X$ 为根的子树内所有节点的权值和。
- 问题本质与核心思路： 子树操作的本质就是 DFS 序的区间覆盖。由于树剖本质上也是一种基于重儿子优先的优先 DFS 序，它保证了任何子树的 DFS 序是一段连续的区间 $[ ext{dfn}[X], ext{dfn}[X] + ext{siz}[X] - 1]$。因此，将树形拍平后，子树修改与查询直接退化为标准的线段树区间加、区间求和问题。
2. 洛谷 P3258 [JLOI2014] 松鼠的新家
- 题意描述： 松鼠要按照给定的 $N$ 个点的序列顺序依次访问树上的节点。每次从当前点走到下一个点，要求路径上经过的所有节点（除起点外）的访问次数加 $1$。求最终每个节点的访问次数。
- 问题本质与核心思路： 路径修改问题。传统的做法需要树剖，但此题为离线静态全量统计。可将树形拍平，利用树上差分思想。对于路径 $(u, v)$，利用 LCA（可通过欧拉序 + ST 表 $O(1)$ 实现），在差分数组上进行操作：$ ext{diff}[u] ightarrow ext{diff}[u] + 1$，$ ext{diff}[v] ightarrow ext{diff}[v] + 1$，$ ext{diff}[ ext{lca}] ightarrow ext{diff}[ ext{lca}] - 1$，$ ext{diff}[fa[ ext{lca}]] ightarrow ext{diff}[fa[ ext{lca}]] - 1$。最终由底向上进行一次子树和（即 DFS 序树形回溯）即可得到真实频次。