树上问题

树本质上是连通且无环的特殊无向图，很多图论通用算法都可以直接作用于树，BFS、DFS 就是十分常用的基础算法。但树拥有独特的层级结构，存在根节点、子节点、祖先与后代的从属关系，基于这种特有性质衍生出许多树专属算法，倍增求解 LCA（最近公共祖先）就是典型例子。倍增 LCA 需要先通过 DFS 预处理倍增表fa[i][j]，其中fa[i][j]表示节点i向上跳跃2^j步抵达的祖先节点；查询两个节点的最近公共祖先时，先借助倍增数组将深度更大的节点向上提升，直至两个节点深度一致，随后两点同步向上倍增跳跃，最终找到二者最近公共祖先p。

在 LCA 的基础上可以解决大量树上两点路径统计问题。若统计点权路径和，令dis[x]代表根节点到节点x路径上所有点权之和，u,v两点路径和满足dis[u] + dis[v] - dis[p] - dis[fa[p][0]]；若是边权路径和，dis[x]定义为根到x所有边权之和，公式为dis[u] + dis[v] - 2 * dis[p]，p依旧为LCA(u,v)。异或运算存在特殊性质，路径异或值无需带入 LCA 参与计算，根到各点路径异或值记为dis[x]，则u到v路径异或等于dis[u] ^ dis[v]。

面对需要动态修改、路径区间查询的复杂树上问题，可以采用树链剖分。算法通过划分重儿子、轻儿子，把整棵树切割为数条重链，每条重链映射成一段连续线性区间，从而借助线段树、树状数组等线性数据结构维护信息。查询两点路径信息时，不断将所在链顶端深度更深的节点向上跳跃，分段累加每条重链的信息直至两点落在同一条链上，整套向上跳链的思想和 LCA 向上寻找祖先的逻辑相通，树链剖分本身也可以直接用来求解 LCA。