沙茶出题人数据造出锅了,还要大家来帮他修.
甚至连个题解都没有.
$A$
考虑换根,若当前根节点从 $u$ 换到 $v$ ,显然只有 $u$ 和 $v$ 的贡献会改变.
预处理一大堆东西,从 $u$ 换到 $v$ 时更新贡献,回溯时撤回.
时间复杂度 $O(n)$ .
$B$
将每次变换看做一个矩阵,转化为矩阵的 $BSGS$ .
由于矩阵可能没有逆,所以最后再判一下解是否合法.
时间复杂度 $O(T\cdot \sqrt P\cdot \log \sqrt P )$ .
$C$
将每个数看做 $0/1$ 串,正着建一棵字典树,反着建一棵字典树.
那么每个前缀武器就能在前缀的字典树树上割下一颗子树,每个后缀武器能的后缀的字典树上割下一颗子树.
每个给出的点在两棵树上至少被割掉一次,可以将两颗树拼在一起,建立一个最小割模型.
