题解

思路

先把“能否补全为相同多重集合”改写为每个节点上的二十六个路径最大值约束。单次修改只会让某个字母的最大值在一段连续祖先链上增减；用叶序线段树找出这段祖先链，再用树链剖分维护所有节点是否仍满足约束。

做法

可行性刻画

若叶子深度不全相同，所有路径长度不同，答案永远是 Fou。以下设所有叶子深度相同。

对节点 $u$、字母 $c$，定义 $M_u(c)$ 为从 $u$ 到其子树内任意叶子的路径中，固定字母 $c$ 的最大出现次数；令 $h_u$ 为 $u$ 到叶子的边数。子树能够补全，当且仅当

对所有节点 $u$ 都成立。必要性显然。充分性可自底向上归纳：在节点 $u$ 选取至少包含各字母 $M_u(c)$ 个的公共多重集合，剩余位置任意分配；每个孩子所需的多重集合都被它包含，缺少的字符正好可由该路径上的问号补齐。

在根节点记 $D=h_1$、$S=\sum_cM_1(c)$。对一个固定字母 $c$，可以把全部 $D-S$ 个自由位置都填成 $c$，所以

于是答案为

子任务 1：逐次重算

每次修改后，自底向上计算所有 $M_u(c)$ 和 $h_u$，并检查全部节点。每条父子边只参与二十六个字母的转移。

单次复杂度 $O(26n)$，总复杂度 $O(26nq)$，空间复杂度 $O(26n)$。

子任务 2：只有一个固定字母

只有 a 与 ? 时，约束恒有 $M_u(\mathtt a)\le h_u$。按 DFS 叶序排列所有叶子；一条边的字符从 ? 变成 a，等价于给该边下方连续叶区间的根到叶固定 a 数全部加一。区间加、全局最大值用懒标记线段树维护。

若根到叶深度为 $D$，全局最大值为 $m$，答案是 $m+351(D-m)$。每次更新复杂度 $O(\log n)$。

子任务 3：树是一条链

只有一个叶子时必然可行。直接维护二十六个固定字母计数；修改一条边只需删去旧字符并加入新字符。每次更新复杂度 $O(1)$。

满分算法

仍按 DFS 叶序排列叶子。对每个字母 $c$ 建一棵支持区间加与区间最大值的线段树，维护每个叶子的根到叶固定 $c$ 数，记为 $A_c$。于是一个节点 $u$ 对应叶区间上的最大值就是

考虑把边 $(p_x,x)$ 从 ? 改为字母 $c$。修改前令

从 $x$ 向上，子树区间最大值等于 $t$ 的节点构成一段连续祖先链。只有这段链中除 $x$ 外的祖先，其 $M_u(c)$ 会增加一；到达第一个最大值大于 $t$ 的祖先后，更高祖先也不会改变。用倍增从 $x$ 向上跳，并以叶序线段树区间查询判定最大值是否仍为 $t$，即可找到最高端点。随后给 $x$ 的叶区间加一。

删除字母时先给 $x$ 的叶区间减一，再以新的区间最大值同样向上找；对应祖先链上的 $M_u(c)$ 减一。

树链剖分维护每个节点

上述连续祖先链对应一次路径加减。全树最大 $G_u\le0$ 当且仅当全部可行性约束成立。根节点的二十六个 $M_1(c)$ 就是二十六棵叶序线段树的全局最大值，据此直接计算答案。

复杂度

逐次重算层总复杂度为 $O(26nq)$。单字母层每次更新 $O(\log n)$，链形层每次更新 $O(1)$。

满分算法预处理复杂度 $O(26n\log n)$；每次更新使用倍增区间查询与树链路径修改，复杂度 $O(\log^2 n)$。空间复杂度为 $O(26n+n\log n)$。

正确性说明

节点约束的必要充分性说明了全树可行恰等价于所有 $G_u\le0$。叶序区间最大值精确给出各子树内某字母的最大固定次数；单边修改后，受影响祖先恰是“修改前或修改后最大值仍等于目标值”的连续链，倍增找到的端点与该定义一致。树链剖分对这条链作同样的增减，因此始终维护真实的 $G_u$。可行时，根节点公式又逐字母给出了可达到的最大出现次数，故输出值正确。