二叉树

先序遍历：先遍历根节点，然后遍历左节点，最后遍历右节点

中序遍历：先遍历左节点，然后遍历根节点，最后遍历右节点（大概可以理解为把树平面投影至二维从左到右）

后序遍历：先遍历左节点，然后遍历右节点，最后遍历根节点

树上差分 Adjacent Difference on Tree

问题 每次操作将树上u→vu\to v 路径上的所有点权增加dd，求每个点的点权。

思路 用类似前缀和的思想存储树上的点权。用 val[p] 存储pp 节点上方的点权增加值，对于上述操作，按差分思想，只需

1
2
val[u] += d;  val[v] += d;
val[lca(u,v)] -= d;  val[p[lca(u,v)] -= d;

复原时，从根节点开始一步步累加。

1
2
3
4
5
6
7
void dfs2(int u, int p = 0) {
    for (auto& v : E[u]) {
        if (v == p) continue;
        dfs2(v, u);
        val[u] += val[v];
    }
}

变式 每次操作将树上u→vu\to v 路径上的所有边权增加dd，求每条边的边权。

思路 将边权存储在点上（对于树，从根向叶方向，子节点的父节点是惟一的。点上存储的边权即是与父节点相连的那一条边的边权。在 DFS 建树时，遍历每条边时存储这个边权），用 val[p] 存储pp 节点上方的边权增加值，对于上述操作，只需修改为

1
2
val[u] += d;  val[v] += d;
val[lca(u, v)] -= 2d;