一个初步的思路是分析答案二叉树，答案构成 $2n-1$ 个节点、$n$ 个叶子的二叉树。但是这个结构看起来没有什么前途。
由于每个点都有机器人，因此假设 $x,y$ 到 $z$ 合并，可以通过调整法证明，存在最优解满足 $z$ 在 $x,y$ 合并之前不会动，且 $z$ 第一次合并在原地（和 $x,y$ 合并）。
因此可以将这种合并的形态改为 $x,y$ 连向 $z$，$x,y$ 是 $z$ 的儿子。这样树一共只有 $n$ 个点，但并非二叉树。
操作步骤形如挨个剥叶子，一个点必须在所有儿子合并结束后才可以动，考虑第一步剥叶子的形态，假设一个点 $x$ 是叶子，其父亲为 $y$，那么 $x$ 到 $y$ 合并的代价是 $\text{dis}(x,y)+a_y$。
考虑对第一步的一个贪心，对每个点求出 $c_i$ 表示 $\arg \min\limits_{v} a_v+\text{dis}(i,v)$，然后所有点都去 $c_i$ 合并。
考虑之后怎么做，由于此时每个点的位置的 $c$ 都是其本身，所以之后不会出现 $x,y$ 两点走到 $z$ 合并的情况，要么 $x$ 去 $y$，要么 $y$ 去 $x$。
这是一个经典的 MST 问题（CF1305G），将所有 $c_x=x,c_y=y$ 的 $(x,y)$ 连接边权 $a_x+a_y+\text{dis}(x,y)$ 的边跑出 MST，最后假设根节点是 $t$，那么所有 $\neq t$ 的点的 $a$ 都会被多算一次，因此将 MST 总权值减去 $\sum a$，再加上 $\min a$ 就是答案。
由于 $c$ 相同的位置构成连通块，显然只连接相邻连通块之间的 $c$ 必定不会漏掉 MST，因此这部分复杂度为 $O(m\log m)$。
求 $c$ 可以使用多元 dij $O(m\log m)$ 求出，总复杂度 $O(m\log m)$。
接下来证明第一步剥叶子的局部最优等价于整体最优。
我们将 $(i,fa_i)$ 的合并代价在 $i$ 结算。进行两类调整：
- 将所有 $c_u\neq u$ 的点 $u$ 父亲调整为 $c_u$。
- 假设 $u$ 的父亲为 $v$，$v\neq c_u$。
- 将 $u$ 的父亲调为 $c_u$ 一定不劣，这种操作会让答案减少 $\text{dis}(u,v)+a_v-\text{dis}(u,c_u)+a_{c_u}$，根据 $c$ 的定义该值非负。
- 将每个 $c_u\neq u$ 的点调整为叶子。
- 这一步调整干的事情是，确保不存在一个 $c_u\neq u$ 的点 $u$ 是一个 $c_v=v$ 的点 $v$ 的父亲。
- 此时，我们将 $c_v$ 的父亲调整为 $c_u$，和第一步的调整同理，这一步调整会让答案减去一个非负数。
进行第一步剥叶子后，【之后不会出现 $x,y$ 两点走到 $z$ 合并的情况，要么 $x$ 去 $y$，要么 $y$ 去 $x$】的结论也可通过类似的调整法说明。