官方题解只能做到 $O(n^2)$？玩的太差了。可以将逐个枚举终点、重新合并整棵树的 $O(n^2)$ 做法，降到确定性的 $O(n\sqrt{n\log n})$ 时间、$O(n\log n)$ 空间。这里不是给平方算法加剪枝，而是把所有终点的大部分计算批量完成，再利用字符串周期性控制剩余工作量。公开题解中的逐终点合并算法为 $O(n^2)$。
下面给出推导和完整实现。
从无限行走到折叠计数
把根到一个节点的路径写成一个只含 L、R 的字符串，也用这个字符串表示节点。记输入树的节点集合为 $T$，根对应空串 $\varepsilon$。因为输入是一棵包含根的连通子树，所以 $T$ 对取前缀封闭。题目要求机器人从根开始，无限重复一段指令，最终访问 $T$ 中所有节点。([QOJ][2])
固定第一轮结束的位置 $w$，令 $d=|w|$。第一轮从根出发且合法，因此整轮中任意时刻的深度变化非负。于是第二轮完全是第一轮在 $w$ 的子树内的平移，后续各轮依次从 $w^2,w^3,\ldots$ 出发。
只需考虑 $w\in T\setminus{\varepsilon}$。如果第一轮回到根，以后不会访问任何新位置；直接遍历整棵树并停在一个叶子就更短。如果第一轮结束在 $T$ 外，那么以后也不可能访问新宝藏，同样不会优于遍历整棵树后停在最深叶子的方案。
对任意字符串 $x$，不断删除其开头完整的 $w$，直到不能再删，记剩余字符串为 $\rho_w(x)$。例如，当 $w=\texttt{LR}$ 时，$\rho_w(\texttt{LRLRLL})=\texttt{LL}$。
把剩余字符串相同的节点视为同一个节点，得到的图由一个长度为 $d$ 的环，以及挂在环上的若干棵树组成。环上的节点恰好对应 $w$ 的所有真前缀。设输入节点折叠后共有 $m_w$ 个不同节点。
原机器人的一轮行走投影到这个图上，是一个沿环净前进一圈的闭合行走。为了收集所有宝藏，它必须访问全部 $m_w$ 个节点。环上每条边至少走一次，其他边至少往返一次；反过来，在每个环上节点先遍历挂树，再沿环前进一步，就能达到这个下界。因此固定终点 $w$ 的最优答案恰好是
$$ C(w)=d+2(m_w-d)=2m_w-d. $$
令 $D_w=n-m_w$，即折叠过程中减少的节点数。目标便是求所有候选的 $2(n-D_w)-|w|$ 的最小值。
首先可以排除所有非本原串：如果 $w=v^k$，其中 $k\ge 2$，那么继续按照 $v$ 折叠，原来长度为 $k|v|$ 的环会缩成长度为 $|v|$ 的环，至少再减少 $(k-1)|v|$ 个节点。因此 $m_v\le m_w-(k-1)|v|$，进而 $C(v)\le C(w)-(k-1)|v|< C(w)$。
注意，这里说的是终点路径 $w$ 不能是一个更短字符串的整数次幂，不是说指令串里不能出现重复。
接下来，把 $D_w$ 拆成容易批量计算的部分和少量修正。定义 $A_w=|{x\in T:wx\in T}|$，即同时存在 $x$ 和 $wx$ 的节点对数。
考虑一个折叠等价类，其成员可以写成 $w^k r$，其中 $r$ 不以 $w$ 开头。设实际存在的指数集合为 $K$。如果 $K$ 有 $c$ 个元素，分成 $t$ 段连续整数区间，那么这个等价类对 $D_w$ 的贡献是 $c-1$，对 $A_w$ 的贡献则是 $c-t$。两者相差 $t-1$。
也就是说，$A_w$ 已经统计了相邻周期之间的重合，只会漏掉中间隔着空缺周期的重合。
例如，$r$ 和 $w^2r$ 都存在，但 $wr$ 不存在时，它们仍会折叠到一起，而 $A_w$ 无法发现这一点。所有需要修正的位置都位于 $w^2$ 的子树中。
亚平方地算出所有候选答案
先批量计算全部 $A_w$。
在输入的二叉 Trie 上建立 AC 自动机。对于一个节点 $y$，它的路径串有哪些后缀属于 $T$，恰好由 $y$ 在失配树上的祖先给出，包括自身和根。
因此，每一对“$x$ 是 $y$ 的失配树祖先”，都对应一个分解 $y=wx$。这里的 $w$ 是原树上 $y$ 的祖先，其深度为 $\operatorname{dep}(y)-\operatorname{dep}(x)$。这对节点应当给 $A_w$ 加一。
问题转化为：对所有失配树祖先对，把贡献加到原树上相应深度的祖先。
直接枚举这些节点对仍然可能是平方的。我们对失配树分块，块大小参数为 $B$。
从下往上合并尚未分组的节点，累计达到 $B$ 个便取出成为一组。每组至多有 $2B-1$ 个节点，并拥有一个不在组内的公共边界祖先 $b$；组内任意节点到 $b$ 的路径，除 $b$ 外都留在组内。最后剩余的节点单独成为一组。因此一共有 $O(n/B)$ 组。
对组内节点 $y$，将它的失配祖先分为两部分：从 $y$ 到 $b$ 之前的局部部分，以及从 $b$ 到失配树根的公共部分。
局部部分每个节点只需枚举 $O(B)$ 个祖先，总计 $O(nB)$。按原树前序遍历处理 $y$，维护当前根路径数组，就能用目标深度直接取出原树祖先，每次贡献只花 $O(1)$，不需要额外的倍增查询。
对于公共部分，固定一组 $G$，令 $a_y=[y\in G]$，并令 $f(t)$ 表示 $b$ 的失配祖先中是否存在一个原树深度为 $t$ 的节点。由于失配祖先的字符串长度严格递减，$f(t)$ 只会是 $0$ 或 $1$。
这一组对原树节点 $v$ 的贡献就是 $H(v)=\sum_{y\in T_v}a_yf(\operatorname{dep}(y)-\operatorname{dep}(v))$，其中 $T_v$ 表示原树中 $v$ 的子树。
关键在于，给定任意节点权 $a$ 和数组 $f$，所有 $H(v)$ 可以在 $O(n\log n)$ 时间内一起求出。
对此使用长链分解，重儿子必须选择高度最大的儿子，不是子树最大的儿子。设一条长链为 $v_0=h,v_1,\ldots,v_{\ell-1}$，那么 $\ell=\operatorname{height}(h)+1$。所有长链互不相交，所以它们的长度之和为 $n$。
对每个链头 $h$，维护其整棵子树的深度权值和 $P_h[t]=\sum_{y\in T_h,\ \operatorname{dep}(y)-\operatorname{dep}(h)=t}a_y$。数组长度恰好为这条长链的长度。
所有这些数组可以在线性时间内求出：先在链上各位置放入对应节点的权值，然后从下往上，将每个轻儿子的数组平移后加到父长链。每条非根长链的数组只会被合并一次，而所有数组长度之和为 $n$。
再计算 $Q_h[k]=\sum_{t\ge k}P_h[t]f(t-k)$。将 $P_h$ 翻转后与 $f$ 的前 $\ell$ 项卷积，结果的第 $\ell-1-k$ 项就是 $Q_h[k]$。
$Q_h[k]$ 与所需的 $H(v_k)$ 很接近：它还包含了挂在 $v_0,\ldots,v_{k-1}$ 上、并且深度足够大的轻子树。
这些多算的部分同样可以整段扣掉。假设轻儿子 $r$ 挂在 $v_i$ 上，那么它对位置 $v_{i+1+j}$ 的多余贡献恰好是 $Q_r[j]$。所以每条长链的 $Q$ 数组只需要做两件事：加到自己的链上；如果不是根链，再从父长链中对应的一段减掉。
选择最高儿子作为重儿子，保证这段减法不会越过父长链末尾。每条链只进行一次卷积，故总时间为 $\sum_h O(\ell_h\log\ell_h)=O(n\log n)$，卷积之外的工作都是线性的。
于是，所有组的公共贡献总共需要 $O(n^2\log n/B)$ 时间。
还剩下跨周期重合的修正。 对一个本原候选 $w$，如果 $w^2\notin T$，就没有修正；否则只遍历 $w^2$ 的子树。
遍历时不断删除完整的前缀 $w$，得到每个节点的等价类代表 $r$。对于节点 $y=w^k r$，这里必有 $k\ge2$：
若 $w^{k-1}r$ 不存在，那么它是一个新的连续区间的开头，先将修正量加一。随后，如果这个等价类中的 $r$ 和 $wr$ 都不存在，就需要对这个等价类额外减一，因为它最早出现的连续区间不应计入“额外的区间数”。对这些等价类去重后统一扣除即可。
“删除若干个前缀 $w$ 后得到的后缀是否属于 $T$”可以在失配树上按目标字符串长度倍增查询。等价类去重使用精确的字符串倍增编号，而不是随机哈希。
为什么只遍历这些子树，总量不会再次达到平方？
使用三平方前缀引理：若三个本原串的平方依次是真前缀，长度分别为 $d_1< d_2< d_3$，则 $d_3\ge d_1+d_2$。所以任意长度不超过 $n$ 的字符串，只有 $O(\log n)$ 个本原平方前缀。([125 Problems][3])
固定一个原树节点 $y$，它只会被那些“$w^2$ 是其路径串前缀”的候选遍历。这样的本原 $w$ 只有 $O(\log n)$ 个。因此所有修正遍历的节点数之和为 $O(n\log n)$，加上倍增查询和排序，总修正时间为 $O(n\log^2 n)$。
字符串预处理也不需要显式展开所有根路径。把从节点向上长度为 $2^j$ 的字符串排序编号，每一级由两个上一级编号组成。任意长度的字符串可用首尾两个重叠的等长块精确标识。配合原树倍增，可以在 $O(\log n)$ 时间内比较两个路径后缀。
判断长度为 $d$ 的路径串是否本原，只需枚举 $d$ 的不同质因子 $p$，检查 $d/p$ 是否为其周期；若一个字符串是非平凡整数次幂，必然有一个这样的质因子能发现它。全部预处理耗时 $O(n\log^2 n)$。
最终，总时间为
$$ O\left(nB+\frac{n^2\log n}{B}+n\log^2 n\right). $$
取 $B=\lceil\sqrt{n\log n}\rceil$，得到 $O(n\sqrt{n\log n})$ 时间、$O(n\log n)$ 空间。
这是一个可证明的确定性亚平方上界；这里没有证明与之匹配的下界。