1 引入

图1: 二叉树示例

对于一个二叉树，从根节点出发，使用由LR组成的字符串表示路径，则对于每一条路径可以唯一表示每一个节点。如图1所示：4号节点可以对应字符串 LR，2号节点对应字符串R。特别的，根节点对应的字符串为空字符串。

类比于二叉树，可以通过扩展LR的字符集，来适应一个节点有超过两个孩子节点的情形，例如图2中的4号节点，可以用字符串C来表示。

图2：一般的树结构

设 $V$ 是树的节点集合，则可以通过上述过程，将每一个节点映射成一个字符串，设字符串的集合为 $S$ ；
定义函数 $f, g$ ，使得 $\forall v \in V, f(v) = s, s \in S$ 以及 $\forall s \in S, g(s) = v, v \in S$ ；
定义 $ancestor(v) \subset V(v \in V)$ 是一个集合，该集合的所有节点均是 $v$ 的祖先节点；
定义 $distance(u, v), (u, v \in V)$ 为 $u$ 节点和 $v$ 节点之间的距离；
定义 $lca(u, v) \in V(u, v \in V)$ 是一个节点，表示 $u$ 号节点于 $v$ 号节点的最近公共祖先。在图1中， $lca(3, 4) = 1$ 而 $lca(4, 2) = 0$ ；
假设 $s$ 是一个长度为 $n$ 的字符串，则 $prefix(s) = \{s[0], s[0..1], s[0..2], \cdots, s[0..n-1]\}$ ，用于表示字符串 $s$ 所有的前缀的集合；
假设 $S'$ 是一个字符串结合， $longest(S') = s$ ， $s$ 是 $S'$ 中最长的字符串之一，且在最长的字符串中字典序最大；
假设 $s$ 是一个字符串， $length(s)$ 表示字符串 $s$ 的长度。

对于任意的字符串和，分别对应树中的节点和，有：
1. 如果 $s_1 \in prefix(s_2)$ ，那么节点 $v_1 \in ancestor(v_2)$ 。
2. $lca(v_1, v_2) = g( longest(prefix(s_1) \cap prefix(s_2)))$ 。
3. $distance(v_1, v_2) = length(s1) + length(s2) -length(f(lca(v_1, v_2))$