$T_3$ 打了 $\mbox{5kb}$ ,前前后后打了 $7$ 个错误版本,还都过了大样例.
$string$
显然,答案与操作顺序无关,直接把所有 $a$ 移到最前面,这样 $b$ 的个数会翻倍,记录一下 $b$ 的数目即可.
$number$
直接数位 $dp$ ,注意特判 $k=0,1$ 的情况.
$city$
先跑一次 $dfs$ ,把环上所有点依次存下来.
考虑用环上的点把所有点分成若干块,每个点属于离它最近的环上的点.
答案分为两种情况,一种情况是两个端点在同一块,这部分贡献就是若干棵子树的直径最大值,仍然用 $dfs$ 求出.
另一种情况是两个端点在不同块,显然要经过环上点.
对环上的第 $i$ 个点,记录 $d(i)$ 表示这个点到它的那一块中的点距离最大值.
枚举断掉环上的哪一条边,环变成一条链,可以钦定一个起点,记 $H(i)$ 表示此时起点到环上第 $i$ 个点的路径长度.
如果此时选择了环上的第 $x,y$ 个点来更新答案,贡献就是 $d(y)+H(y)+d(x)-H(x)$ ,且必须 $x\not= y$ .
用线段树维护一下 $d+H,d-H$ 的最大值,最大值取到的位置 ,次大值,就可以计算出断掉某一条边的贡献.
当断边切换时,所有 $H$ 都会同时减少一个值,原端点的 $H$ 又加上所有环上边的长度,利用线段树可以维护.
时间复杂度 $O(n\log n)$ .