题目名是一首歌。

最大值最小化，考虑二分答案，转向判断是否存在一条 $1\to n$ 的路径满足权值 $\le mid$。

我们考虑二分答案其实是给每条边加了一个限制，也就是权值为 $w_i$ 的边最晚在 $\lfloor \frac{mid}{w_i} \rfloor$ 时经过。之后不再合法。

我们考虑路径的形态，从而帮助我们理解这个问题。我们知道，如果 $1\to 2$ 和 $1\to 3\to 2$ 同时合法，那么我们一定会选择 $1\to 2$ 这条路径。

显然在合法的前提下，我们会尽可能地走最短路。这其实是一个贪心的思想。可以理解为，走最短路可以达到更多的后继状态，所以一定优于不走最短路。

于是变成了一个边权为 1 的最短路问题，bfs 求解即可。时间复杂度 $\mathcal O(n\log w)$。

这题有着高达 80 的 dp 部分分，并不是很理解为什么场上没有人打。

view in my cnblogs.

两年前的我这么强吗，还会写 30pts，现在的我 30pts 都写不出来。这种字符串工业太可怕了！

好吧，其实做法的提示性很强，这个东西明摆着是让你根号分治的。难点在于维护而不在于贪心。

我先口胡一个东西看看对不对啊。跑 SA，设阈值是 $B$，然后 $\gt B$ 的直接二分出来 $\rm sa$ 范围，然后扔主席树上不停进行区间查询时间复杂度是 $\mathcal O(\frac{nq}{B}\log n)$ 的一个东西。然后 $\le B$ 的子串只有 $\Theta(nB)$ 个。怎么预处理来着？

哦好像题目里规定了 $\le B$ 的很少，$r-l$ 随机均匀这个性质咋用？是想告诉我默认 $\tilde O(r-l)=1000$ 吗？

那我是不是还是可以和上面那个东西一样暴力跑啊 /qd。

看一眼 myee 的题解，好像还真行，$X=50,Y=2000$ 的话这个东西的复杂度就是

$$\mathcal O(\frac{\log n}{Y-X}\int_X^Y \frac{n}{x}\, \mathrm d x) = \mathcal O(n\log n\frac{\ln Y - \ln X}{Y-X})$$

我不会微积分啊，这个式子是抄的。写完这个一定要学一学微积分，要不然这种细致复杂度分析不会做 /ng。（学不会，开摆）

好像还有 $r-l\le X$ 的情况，这个咋办来着。

一般来说字符串这种东西可以反着来，想一想出题人会怎么卡。他要卡我的话肯定能匹配的越多越好，那这样的话询问的本质不同串是不是不会多。

看题解。好吧，首先按上面的方法找到第一个位置，然后倍增预处理就行。不想写代码，啥时候闲的蛋疼了再写。

从整张图入手，有两种方法可以得出这道题的结论。

高斯消元：把矩阵列出来，不难发现矩阵的秩为 $n-1$，那么方案数即为 $2^{m-n+1}$。

构造法：我们考虑一棵树。根据经典的剥叶子型构造手法，我们可以得出一棵树的时候方案数唯一，除非要求 $1$ 的点数为奇数，那样状态异或和为 $1$，而我们的操作状态异或和始终为 $0$，所以构造不出来。反之我们随便抽出来一棵生成树，对于其它边，显然取或不取只会反转两个点的状态，而我们的构造法永远可以构造出唯一解，所以方案数就是 $2^{m-n+1}$。

然后我们考虑这个原问题。图上就那么几个知识点，这题又和割点强相关，那就考虑广义圆方树。

假设一开始有 $\rm cnt$ 个连通块，$i$ 有 $\mathrm{deg}_i$ 条连边，和 $\mathrm{cut}_i$ 个方点相连，并且 $i$ 断开后没有一个连通块内有奇点，那么方案数就是 $2^{m-n-\mathrm{deg}_i+\mathrm{cnt}+1+\mathrm{cut}_i}$。时间复杂度 $\mathcal O(Tn)$。甚至不用显式地建出来圆方树，因为我们只需要 $\rm sz$ 和 $\rm cut$ 两个数组，直接求割点就行。

这是一个 $k + 1$ 维偏序问题，如果使用 CDQ 分治的话将收获 $\mathcal O(n\log^k n)$ 的复杂度，而 $n = 40000$ 的情况下 $\log^k n$ 在这题已经是 $10^6$ 的量级，甚至跑不过暴力 $\mathcal O(n^2k)$。

考虑 bitset，我们用 $S_i$ 的一个 bitset 存储当前所有维度均小于 $i$ 的节点，每次对新的维度排序，然后 bitset and 一下即可。不难发现这样可以正确维护。

时间复杂度 $\mathcal O(\frac{n^2k}{\omega})$，其中 $\omega$ 是计算机位数，一般取 $\omega = 32\ \mathrm{or}\ 64$，跑得飞快，比一些实现的不好的 KDTree 正解还要快。

nfls 集训的作业题。

考虑 dp。设 $f_i$ 表示前 $i$ 个串的最小代价，$s_i$ 为前缀和，则：

$$f_i=\min_{j\in [0,i)} f_j+|s_i-s_j+i-j-L-1|^p$$

然后发现右边的东西关于 $s_i+i-L-1$ 是一个对称的东西，而且二阶导恒非负。这个时候考虑使用二分队列优化决策单调性。

考虑用三元组 $\left\langle j, l, r \right\rangle$ 表示 $l\to r$ 内的最优决策点为 $j$。

遍历 $i:1\to n$，当队首的 $r\lt i$ 的时候先扔掉，然后令 $l=i$。

对于队尾的一些 $\left\langle j,l,r \right\rangle$，如果 $i\to l$ 的决策比 $j\to l$ 的决策更优，根据决策单调性，$[l,r]$ 内的决策都是 $i$ 更优，直接舍弃 $j$，更替为 $i$。

如果我们弹出的过程中遇到了第一个不满足上述条件的 $\left\langle j,l,r \right\rangle$，那么一定存在一个决策点 $p\in [l,r]$，满足 $\forall x\in [l,p]$，$j$ 更优，$\forall x\in [p+1,r]$，$i$ 更优。直接二分出来就行。

时间复杂度均摊 $\mathcal O(n\log n)$。

COGS 为啥不支持 LaTeX 的 \binom，只能用 $\mathrm C$ 表示组合数了。

非常暴力的组合数计数。

考虑拆贡献，对 $i$ 节点，我们枚举 $k = sz_i$，计算 $i$ 子树大小为 $k$ 的方案数，然后直接暴力乘起来。

$i$ 子树内的方案数是 $$(k - 1)!\times \mathrm C_{n - i}^{k - 1}$$

表示 $\gt i$ 的树中选 $k - 1$ 个进行排列，然后 $i$ 子树外的方案数是 $i!\times (i + 1 - 2)\times (i + 2 - 2)\dots \times (n - k + 1 - 2) = i\times (i - 1)\times (n - k - 1)!$。

那么 $i$ 的方案数就是 $$\sum_{k=1}^{n-i+1} k\times (n - k)\times (k - 1)!\times \mathrm C_{n - i}^{k - 1}\times i\times (i-1) \times (n - k - 1)!$$

谔谔，为什么会RE，我干啥了，别的地方都能AC啊。