和次小生成树相似的套路
记f 为S 到所有点的最短路，g 为T 到所有点的最短路
枚举所有边$edge\left \{ u,v,val \right \}$

$$ans=min\left \{ f\left [ u \right ]+val+ g\left [ v \right ]\right \}\left ( f\left [ u \right ]+val+ g\left [ v \right ]>f\left [ T \right ] \right )$$

缩完点之后求有多少入度为0的点即可

$$\left\{\begin{matrix} x\equiv a_{1}\left ( mod \ b_{1} \right ) \\ x\equiv a_{2}\left ( mod \ b_{2} \right )\\ \cdots \\ x\equiv a_{n}\left ( mod \ b_{n} \right )\\ \end{matrix}\right.$$

其中$gcd\left ( b_{i} ,b_{j}\right )=1\left ( i\neq j,i\in n,j\in n \right )$
设

$$M=\prod_{i=1}^{n}b_{i}$$ $$M_{i}=\frac{M}{b_{i}}$$ $$r_{i}\equiv M_{i}^{-1}\left ( mod \ b_{i} \right )$$

则

$$x=\sum_{i=1}^{n}M_{i}a_{i}r_{i}$$

且在M 以内有唯一解

记$dp\left [ i\right ]\left [ j \right ]$为i 节点，取j 个能获得的最大收入
叶节点$dp\left [ i\right ]\left [ 1 \right ]=w\left [ i \right ]$
转移方程

$$dp\left [ x\right ]\left [ i \right ]=max\left \{ dp\left [ to \right ]\left [ j \right ]+dp\left [ x \right ]\left [ i-j \right ]-cost\left [ x \right ]\left [ to \right ] \right \}\left ( to\in x_{son} \right )$$

对顶堆的模板题
对顶堆为一个大根堆A ,和一个小根堆B ,分别维护一个序列的前一段和后一段
要求中位数，只需要将序列均分入两个堆中即可

首先要知道怎么求非严格次小生成树
记$max\left \{ u,v \right \}$为u，v 路径上的最大边权
先求一遍最小生成树，记权值为mins
然后枚举所有不在树中的边$edge\left \{ u,v,val \right \}$
非严格次小生成树的权值为$min\left \{ mins-max\left \{ u,v \right \} +val\right \}$
用倍增或树剖都可以求

现在要求严格次小的
于是记录$\left \{ u,v \right \}$的次大边权，保证其严格小于最大值，记为$nxt\left \{ u,v \right \}$
然后依旧是枚举所有不在树中的边$edge\left \{ u,v,val \right \}$
若$val>max\left \{ u,v \right \}$，则为$mins-max\left \{ u,v \right \} +val$，否则为$mins-nxt\left \{ u,v \right \} +val$

记$dp\left [ t \right ]\left [ i \right ]\left [ j\right ]$为i 到j 经过t 条边的最短路
转移方程为

$$dp\left [ t+1 \right ]\left [ i \right ]\left [ j\right ]=min\left \{ dp\left [ t \right ]\left [ i \right ]\left [ k \right ]+ d\left [ k \right ]\left [ j \right ]\right \}\left ( 1\leq k\leq n \right )$$

通过观察，发现很像矩阵乘法，然后还满足交换律
因此

$$dp\left [ t \right ]=dp\left [ 0 \right ]*D^{t}$$

$dp\left [ 0 \right ]$矩阵中除$dp\left [ 0 \right ]\left [ st \right ]\left [ st \right ]= 0$，其它为INF

直接计算复杂度过高无法接受
考虑枚举所有$gcd$值计算
若$gcd=k$
对于所有$gcd\left ( x,y \right )=1$，有$gcd\left ( xk,yk \right )=k\left ( xk\leq n,yk\leq n \right )$
所以$gcd=k$的个数为

$$2\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\varphi \left ( i \right )-1$$

复杂度$O\left (N \right )$

还有一种更妙的做法
设$f\left [ k \right ]$为$gcd=k$的个数
设$g\left [ k \right ]$为$k|gcd$的个数

$$g\left [ k \right ]=\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor}f\left [ ik \right ]=\left [ \frac{n}{k} \right ]^{2}$$ $$f\left [ k \right ]=g\left [ k \right ]-\sum_{i=2}^{\left \lfloor \frac{n}{k} \right \rfloor}f\left [ ik \right ]$$

倒序计算即可
复杂度$O\left ( NlogN \right )$

想了好久发现套不了数据结构。
然后看了看数据范围用了分块。
分成$\sqrt{n }$个块，块内保持有序
对于M 操作，覆盖整块就打标记，否则暴力更新并重新排序
对于A 操作，覆盖整块就二分查找，否则暴力查找
复杂度$O\left ( QlogN \sqrt{N} \right )$

$$k\ mod \ i=k-\left \lfloor \frac{k}{i} \right \rfloor*i$$ $$\sum_{i=1}^{n}k \ mod \ i=\sum_{i=1}^{n}\left ( k-\left \lfloor \frac{k}{i} \right \rfloor*i \right )=nk-\sum_{i=1}^{n}\left ( \left \lfloor \frac{k}{i} \right \rfloor*i \right )$$

分块求解即可