题意理解

我们有一棵有根树（根为 1），每条边上有一个字符 0 或 1。
定义 $S_u$ 为从根到 $u$ 路径上所有边的字符连接成的字符串。

扩展点：如果 $S_u$ 是 $S_v$ 的后缀，则 $v$ 是 $u$ 的扩展点。

每个点 $u$ 有：

• $val_u$：价值
• $a_u$：限制

过程：

1. Alice 从 $S_u$ 删除末尾 $i$ 个字符，得到 $S'$（长度 $i$ 从 $|S_u|$ 到 $0$）。
2. Bob 收到 $S'$，可以在末尾加字符得到 $S''$。
3. 如果存在 $u$ 的扩展点 $v$ 使得：
   • $S'' = S_v$
   • $|S'| \ge a_v$ 则 Bob 获得 $val_v$，且 Bob 会选择 最大 的 $val_v$。
4. 对每个 $i$ 得到最大收益，求和就是 $ans_u$。

形式化转化

对每个 $u$，求： $ ans_u = \sum_{i=0}^{|S_u|} \max_{\substack{i \ge a_v \\ S_u = S_v[|S_v|-|S_u|+1, |S_v|] \\ S_u[1, i] = S_v[1, i]}} val_v $ 其中 $\text{Ext}(u)$ 是 $u$ 的扩展点集合。

关键观察

1. 扩展点的含义
   $v$ 是 $u$ 的扩展点 ⇔ $S_u$ 是 $S_v$ 的后缀 ⇔ 在 后缀树/后缀自动机 上，$u$ 对应的节点是 $v$ 对应节点的祖先（在反串的 suffix tree 中），但更简单的是：
   在 Trie 上（所有 $S_u$ 插入 Trie），$u$ 对应的节点是 $v$ 对应节点的祖先（因为 $S_u$ 是 $S_v$ 的前缀？注意这里方向反了）。

   实际上 $S_u$ 是 $S_v$ 的后缀 ⇔ 在正串的 Trie 上，$u$ 是 $v$ 的祖先？不，这是前缀关系。
   后缀关系需要反转字符串：定义 $T_u = \text{reverse}(S_u)$，那么 $S_u$ 是 $S_v$ 的后缀 ⇔ $T_u$ 是 $T_v$ 的前缀。

   所以我们可以把每个 $S_u$ 反转，插入 Trie，那么扩展点关系就是 Trie 上的 祖先-后代 关系。

2. 条件 $S_u[1,i] = S_v[1,i]$
   在反转串的 Trie 中，$S_u[1,i]$ 对应 $T_u$ 的前 $i$ 个字符，也就是原串 $S_u$ 的后 $i$ 个字符反转。
   但更简单理解：$i$ 是 Alice 删除后剩下的长度，$S_u[1,i]$ 是 $S_u$ 的前缀，$S_v[1,i]$ 是 $S_v$ 的前缀，要求它们相等。
   在 Trie 上（正串），前缀相等意味着它们有公共祖先在深度 $i$ 处。

   所以我们可以：

   • 将所有 $S_u$ 插入 Trie，每个节点对应一个前缀。
   • 对每个 $u$，在 Trie 上从根到 $u$ 的路径上（深度 $d$ 从 0 到 $|S_u|$），我们考虑深度 $i$ 的节点 $p$，我们要找 $u$ 的扩展点 $v$ 且 $v$ 在 $p$ 的子树中（因为 $S_v$ 的前 $i$ 个字符与 $S_u$ 相同），且 $i \ge a_v$，且 $S_u$ 是 $S_v$ 的后缀。

   但 $S_u$ 是 $S_v$ 的后缀 在 Trie 上怎么体现？
   在正串 Trie 上，$S_u$ 是 $S_v$ 的后缀 ⇔ $u$ 在 后缀树 上是 $v$ 的祖先。
   所以我们需要建立 后缀自动机 (SAM) 或 后缀树 来处理后缀关系。

后缀自动机解法

我们考虑将 所有 $S_u$ 的反串 插入一个广义 SAM。
在 SAM 的 parent 树上，如果 $u$ 对应的节点是 $v$ 对应的节点的祖先，则 $T_u$ 是 $T_v$ 的后缀 ⇔ $S_u$ 是 $S_v$ 的后缀。

所以扩展点关系就是 parent 树上的祖先-后代关系。

问题转化到 SAM 的 parent 树上

对每个 $u$，在 SAM 上找到对应节点 $pos_u$（反串的结束节点）。
那么 $u$ 的扩展点集合 = 在 parent 树中 $pos_u$ 的子树中的所有 $v$。

原问题：
对每个 $u$，对 $i = 0 \dots |S_u|$，求 $ \max_{\substack{v \in \text{subtree}(pos_u) \\ i \ge a_v \\ \text{lcp}(S_u, S_v) \ge i}} val_v $ 其中 $\text{lcp}(S_u, S_v)$ 是最长公共前缀长度。

进一步简化

注意 $\text{lcp}(S_u, S_v) \ge i$ 在 Trie 上（正串）意味着：$u$ 和 $v$ 在深度 $i$ 时有公共祖先。
但 $u$ 的深度 $|S_u|$ 固定，$i$ 是 $u$ 的前缀长度，所以 $v$ 必须和 $u$ 共享前 $i$ 个字符。

在正串 Trie 上，从根到 $u$ 的路径上深度 $i$ 的节点 $p$，我们要找 $v$ 在 $p$ 的子树中，且 $v$ 在 SAM 的 parent 树中在 $u$ 的子树中，且 $i \ge a_v$。

实现方案

1. 建立所有 $S_u$ 的 正串 Trie，记录每个节点对应的 $u$ 集合（可能有多个 $u$ 共享前缀）。

2. 建立所有 $S_u$ 反串的 广义 SAM，记录每个节点对应的 $u$ 集合（可能有多个 $u$ 对应同一个节点，如果它们反串后缀相同）。

3. 在 SAM 的 parent 树上 DFS，得到每个节点的子树中所有 $(a_v, val_v)$ 对。

4. 对 Trie 上每个节点 $p$（深度 $d$），它子树中所有 $u$ 的扩展点 $v$ 满足 $d \ge a_v$ 的最大 $val_v$ 可以预处理：
   对每个深度 $d$，维护一个数据结构，支持：添加 $(a_v, val_v)$，查询所有 $a_v \le d$ 的最大 $val_v$。
   由于 $d$ 从 0 到 $n$，我们可以用线段树按 $a_v$ 存储最大值，查询前缀最大值。

5. 对每个 $u$，在 Trie 上从根到 $u$ 路径上每个深度 $i$，查询该深度节点对应的最大 $val$，然后求和。

算法步骤

1. 读入，建树，得到每个 $S_u$。
2. 建正串 Trie，节点记录深度、对应哪些 $u$ 的路径经过它。
3. 建反串广义 SAM，记录每个节点对应哪些 $u$ 的结束位置。
4. 在 SAM parent 树上 DFS 合并子树信息（$(a_v, val_v)$ 集合）。
5. 在 Trie 上 DFS，进入节点时把该节点在 SAM 中对应集合的 $(a_v, val_v)$ 加入全局线段树（按 $a_v$），退出时撤销。
6. 对每个 Trie 节点 $p$（深度 $d$），记录 $maxval[d] =$ 线段树查询 $[0, d]$ 的最大值。
7. 对每个 $u$，$ans_u$ = 从深度 0 到 $|S_u|$ 的 $maxval$ 之和。

复杂度

• Trie 和 SAM 节点数 $O(n)$
• 线段树更新 $O(\log n)$
• 总 $O(n \log n)$