写题的稿纸，拿来水水题解可能不错？
题号就不写了，自己猜吧。
$f_{e,i,j}$ 表示警察在 $e$ 这条边上，还有 $i$ 个小偷其中 $j$ 个在警察前进方向，剩余最短的时间
$e$ 通向叶子：$f_{e,i,j}=f_{!e,i-j,i-j}+w_e$
$\text{otherwise}:f_{e,i,j}=w+\max_{\sum a_i=j}\min_{k=1}^d f_{e_k,i,a_k}$
$g_{i,j}$ 表示前 $i$ 个儿子放了 $j$ 个小偷 $\sum_{k=1}^i a_k=j$，$f_{e,i,j}$ 最大是多少
$g_{i,j}=\max_{k=0}^j\min(g_{i-1,j-k},f_{e_i,i,j})$
$g$ 总状态 $O(n^2)$ 转移 $O(n)$，$f$ 状态 $O(n^3)$ 转移 $g$ 总共 $O(n^5)$
单调性：$f_{e,i,j}\ge f_{e,i,j+1}$
对于 $f_{e,i,j+1}$ 找一个 $a_k+1$ 一定比其他更优，画图可以证明
因此 $f_{e,i,j+1}=\min(f_{e,i,j},\max f_{e_k,i,a_k+1})$
在 $S$ 上做树形嵌入，然后容斥掉自己和自己的同构
$f_{s,t,S}$ 表示现在将 $s$ 和 $t$ 匹配，其中已经匹配的儿子集合为 $S$ 时的答案
枚举 $s$ 的儿子和 $t$ 的儿子匹配
$f_{s,t,S}=\sum_{s’\in s,t’\in t} f_{s,t,S\oplus s}\times f_{s’,t’,U}$
起始：枚举 $T$ 的根和 $S$ 的哪个节点匹配
$O(T\sum d_id’_i2^{d’_i})\to O(ST^22^T)$
$f_{l,r}$ 表示删去 $[l,r]$ 的代价，但是转移和极差有关
再令 $g_{l,r,mx,mi}$ 表示删去 $[l,r]$ 中一些数使得 $a_i\in[mi,mx]$ 的代价
$f_{l,r}=\min g_{l,r,mx,mi}+a+b(mx-mi)^2$
$g_{l,r,mx,mi}=\min(h_{l’,r’},g_{l,k,mx,mi}+g_{k+1,r,mx,mi})$
可以离散化，状态 $O(n^4)$ 转移 $O(n)$，应该跑不满
初值 $g_{l,l,mx,mi}=0/a$
对每个点分开计算剩余每个点删除时它的贡献
令 $len_u$ 表示 $i\to u$ 上所有的点的个数
树的情况 $i$ 对 $j$ 有贡献，则 $j$ 删除时 $i$ 和 $j$ 联通，也即有 $len_u-1$ 个点在这之后才被删去
$p_{i,j}=\frac{C_{n}^{len_u}(len_u-1)!(n-len_{u})!}{n!}=\frac{1}{len_u}$
枚举 $i$，$f_{u,k}$ 到 $u$ 号点，$i\to u$ 上保留了 $k$ 个点但仍然联通的方案数，带上容斥系数（有多少个地方有两个选择）
$ans_{i,u}=\sum_{k=0}^{len_u} f_{u,k}\frac{1}{k}$
把树边看成二元环，定义 $fa_u$ 表示进入 $u$ 所在环时到达的第一个点，设 $fa_u\to u$ 的两条路径上的点数为 $x,y$
$f_{fa_u,k}\to f_{u,k+x},f_{u,k+y},-f_{u,k+x+y-1}$
状态 $O(n^2)$ 转移 $O(1)$，总 $O(n^3)$
$f_i$ 表示所有排列归并，只有最后 $n$ 个 $i$ 出锅的概率，可以不全部归并完
总方案数 $g_i=\prod_{k=1}^{n}C_{sum_{k-1}+pos_{k,i}-1}^{pos_{k,i}-1}=\frac{(\sum_{k=1}^{n}(pos_{k,i}-1))!}{\prod_{k=1}^{n}(pos_{k,i}-1)!}$
容斥，$f_i=g_i-\sum_{j=1}^{n}[\forall k\in[1,n],pos_{k,j}<pos_{k,i}]w_{i,j}f_j$
$w_{i,j}$ 是转移系数，和 $g_i$ 的式子差不多
在每个排列后加上 $m+1$，答案就是 $f_{m+1}$
直接枚举 $j$ 转移，$O(nm)$，总 $O(n^3m)$
数据随机 $\to w_{i,j}=0$ 的期望区间个数为 $\frac{1}{2^n}+\frac{1}{2^{n-1}}+\cdots+\frac{1}{2}$
总 $O(n^2m)$，$g$ 和 $w$ 在 $dp$ 的时候顺手维护一下
修改部分：邻接矩阵矩形加，关于主对角线重叠的部分要加两遍，可以用扫描线解决
边数很多，考虑使用 $\text{Boruvka}$ 算法，维护每个联通块连出去的最小边
扫描线有个线段树，直接在线段树上维护最小值和连向不同于最小值所在联通块的次小值
从这两个值里选一个加入答案，并用并查集维护联通性
$\text{Boruvka}$ 最多进行 $\log n$ 轮，$O(\log n(n\log n+n)+m)\to O(n\log^2n)$
移动左端点，线段树维护所有右端点答案
联通块数 $=$ 点数 $-$ 边数 $+$ 环数
左端点移动：点移出，边移出，环移出
点：右侧 $-1$，边：另一个端点右侧 $+1$，环：环上最大值右侧 $-1$
线段树区间修改即可，$O(n\log n)$
枚举第一步走到哪里，剩下的部分只要不经过这条边就可以
把边反向跑最短路，不合法当且仅当这个点的最短路是原路走回去的
钦定这条边不能走，直接暴力做 $O(n^2\log n)$
求一个和最短路走的第一条边不同的次短路，如果最短路不行就用次短路
$O(n\log n)$
先令 $sg_1=sg_2=0$，然后向外拓展
$f_S$ 表示只有 $S$ 内的边，满足条件的方案数，尝试拓展到 $T$
枚举 $sg=0$ 的集合 $U$，剩余部分记为 $V$
连边条件：$U$ 内无边，$V$ 中每个点到 $U$ 最少有一条边
令第二个条件的方案为 $cnt_U$，则：
$S$ 包含 $1,2$ 号点：$f_S=\sum_{U}cnt_Uf_{S\oplus U},cnt_U=\prod_{i\in U} 2^{d_i}-1\prod_{i\in V}2^{d_i}$
$S$ 包含 $1,2$ 号点其中一个：$f_S=0$
$\text{otherwise}：f_S=2^p$，$p$ 为边数
相当于枚举子集，$O(3^nm)$
把连边状态压成状态，直接 $\text{count}$，$O(3^nn)$
考虑加点来构造出这个图，把左部点按 $a_i$ 排序，每次相当于：
加上一个右部点，或者加上一个左部点且它向右部所有点连边
维护最终用于构成环的链的数量（从右部点到右部点），则左部点可以将一条链闭合，或者连接两条链
$f_{i,j}$ 表示这个环上，已经添加 $i$ 个左部点，有 $j$ 条链待连接的方案数
这一步添加的是右部点 $f_{i,j}=f_{i,j-1}+f_{i,j}$
这一步添加的是左部点 $f_{i,j}=\frac{j(j+1)}{2}f_{i-1,j+1}+f_{i-1,j},ans+:f_{i-1,1}$
最后要去掉二元环，同时注意到对于一个环，连接最后两条链和将其闭合这两次操作可以对调，所以答案要 $/2$
$O(n^2)$
限制相当于仅可以跳到祖先上第一个权值大于等于这个点的位置
考虑倍增，维护每个点跳 $2^i$ 步后能够到达的点，跳跃满足合并的要求
还有一个总权值和的条件，再记一下跳跃经过的路径总长即可，注意路径合并的时候要减掉多算的一次合并点
每加入一个点，需要找到第一步能跳到的点，这个用倍增也同样可以解决
然后直接处理其的倍增数组即可，$O(n\log n)$
对 $i$ 考虑删去 $j$ ，它的贡献，则此时 $i\sim j$ 的所有数必须在 $j$ 后删除
设 $i$ 和 $j$ 之间的距离为 $len_{i,j}$，则方案数为 $C_{n}^{len_{i,j}}(len_{i,j}-1)!(n-len_{i,j})!=\frac{n!}{j}$，可以预处理后 $O(1)$ 计算
考虑固定 $i$ 移动 $j$ 时，相当于右边少了最大的一个贡献，左边再加上一个贡献
因此可以做到 $O(n)$
分治，每次处理路径跨过第 $mid$ 行的询问
维护上部点能够到达的第 $mid$ 行上的点的集合，能够到达每个下部点的第 $mid$ 行上的点的集合
判断只需要枚举经过第 $mid$ 行的哪个点即可，实际上是一个求交的过程，因此使用 $bitset$ 维护
$T(n)=2T(\frac{n}{2})+\frac{nm^2}{\omega}\to O(\frac{nm^2\log n}{\omega})$，总共是 $O(\frac{nm^2\log n+qm}{\omega})$
同样考虑分治，每次考虑跨过第 $mid$ 行的矩形
枚举矩形的左右边界，把矩形从第 $mid$ 行割开，令 $up_x$ 表示在这个矩形的权值 $\le x$ 的情况下，矩形的上边界，$down_x$ 同理
那么答案就是 $\sum_{x=0}^{k}(up_{x}-up_{x-1})(down_{k-x-1}-down_{k-x})$
考虑怎么求 $up_x$ 和 $down_x$，发现如果固定左端点，随着右端点右移，两个值都具有单调性，并且移动次数不超过 $n$ 次
因此单次求解的复杂度是 $O(mk(m+n))$，$T(n)=2T(\frac{n}{2})+O(mk(m+n))\to O(nm^2k)$
发现瓶颈在 $m$ 上，而行列上的分治本质上是一样的，因此套路性地使用交错分治，使得 $n$ 和 $m$ 同时减小
$T(n,m)=4T(\frac{n}{2},\frac{m}{2})+O(k(n^2+m^2))\to O(k(n^2\log n+m^2\log m))$
一种做法：
点分治，打表发现对一个点， $\gcd$ 不同的路径条数不超过因数个数即 $240$
对每个因数维护一下最长的路径和不在同一个子树内的次长路径，直接暴力合并
$O(\log n(n+240^2))$，处理的时候要聪明一点不然空间会爆炸
另一种做法：
点分治，对每个质因数维护上一种做法中的信息，打表发现质因数个数为 $17984$，而一个数最多有 $7$ 个不同质因子
暴力合并，总复杂度 $O(x+7n\log n)$，其中 $x$ 是预处理的复杂度，大约为 $2\times10^6$
点分治，对每个长度维护最长路径和不在同一个子树内的次长路径，在计算新的子树时一边更新答案一边维护，$O(n\log n)$
点分治，$\gcd$ 不同的路径条数不超过 $160$，直接暴力合并即可，$O(\log n(n+160^2))$
点分治，计算路径长度的时候顺手更新答案，相当于一个二维偏序
如果不是点分治，直接排序 $+$ 树状数组解决，点分治需要把不经过当前根的路径容斥掉
用聪明一点的方法清空树状数组，$O(n\log^2n)$
发现询问对应 $dfs$ 序的一个区间，直接莫队，$O(n\sqrt q)$
大力根号分块，$k$ 大于 $\sqrt n$ 的询问直接暴力跳，小于 $\sqrt n$ 的部分可以用预处理后缀和，$O(n\sqrt n)$
但是如果全部预处理空间会被卡，把需要预处理的询问离线下来，对每个需要知道的 $k$ 算一遍即可
$k\ge\sqrt n$ 的部分只能跳 $\sqrt n$ 次，暴力做就好了
对剩下部分，容易发现知道 $p$ 和 $k$ 后，答案是固定的，直接预处理，总共是 $O(n\sqrt n)$
数据范围这么大，显然不能 $\text{dp}$，考虑贪心
先将每个右端点的可行区间中最优的左端点塞到堆里，选出最大的数后，此后这个可行区间要挖掉这个数，相当于把它劈成两半
只需要求区间最值及其位置即可，$\text{ST}$ 表或者直接线段树，$O((n+k)\log n)$
结论：答案必定包含直径的一个端点，分类讨论证明即可
预处理出直径的两个端点，以它们为根，则答案变成根开始的一条路径，修改就是子树异或，全局查询值为 $0$ 的最深的点
转成 $dfs$ 序后，用线段树维护，$O(m\log n)$
将序列用 $0$ 分割开，则操作相当于在任意两段间移动偶数个 $1$
于是可以发现，操作不改变每一段的奇偶性，因此两个序列可达当且仅当所有对应的两段奇偶性全部相同
类似分块的思想，询问可以分成头尾的散段和中间的整段，而整段可以通过预处理直接哈希判断
散段的 $1$ 的个数可以用 $\text{set}$ 很轻松的求出，$O(q\log n)$
直接排序不好搞，但是对 $0-1$ 序列排序很容易，只需要线段树维护 $0-1$ 的个数然后区间赋值即可
套路性地，我们直接二分最后的答案，把原序列按大小转成 $0-1$ 序列然后维护即可，$O(n\log^2n)$
把一个点拆成 $n+m$ 个点，表示这个点还能免费走几步，显然掉头只会让答案变得更劣，所以不会有影响
直接在上面跑 $\text{Dijkstra}$ 就行了，$O(n^3\log n)$
看到树上路径直接大力点分治，对分治点，需要知道所有路径的 $a=\sum_{i=1}^{len}iv_i$ 和 $b=\sum_{i=1}^{len}(len-i+1)v_i$，以及 $c=\sum_{i=1}^{len}v_i$
注意到权值为正，因此不难发现路径的两个端点必定都在叶子结点上
枚举两条链 $u,v$ 合并，答案是 $a_u+len_a\times c_v+b$，对每个 $len$ 只需要维护 $a$ 最大的那个值就好了
接下来只需要枚举 $len_a$，快速得到对所有的 $v$，$len_a\times c_v+b$ 的最大值即可，这个东西显然是个一次函数，使用李超树维护
由于插入的实际上是直线，因此李超树可以少一个 $\log n$，总共 $O(n\log^2n)$
离散化后对每种颜色分别计算，令该种颜色的位置上的权值为 $1$，其他为 $-1$，则问题转化为求区间和 $>0$ 的区间的个数
前缀和一下，问题变为对每个右端点，求权值小于它的左端点的个数，这样复杂度还是太大
为了使复杂度正确，每个位置应当只处理一次，因此只能暴力计算权值为 $1$ 的位置互相之间的贡献，考虑如何快速计算两个 $1$ 之间的的 $-1$ 的贡献
首先，一段内的 $-1$ 互相之间显然不会有贡献，只需要考虑两段间的 $-1$
建出权值线段树，假设这一段的前缀和为 $s_1\cdots s_k$，前缀和为 $i$ 的左端点有 $buc_i$ 个，那么答案会加上 $\sum_{i=1}^{k}ibuc_{s_i}$
令 $s_k=x$，那么也可以写成 $\sum_{i=1}^k(k-i+1)buc_x$，这是经典问题，线段树上每个节点再维护 $\sum_{i=1}^{len}(len-i+1)val_{i}$ 即可
处理完以后更新信息相当于一个区间加，$1$ 和 $-1$ 之间的贡献也很好解决，$O(n\log n)$
显然二分，$n$ 很大，剩下的部分被复杂度限制不大能 $\text{dp}$，考虑贪心
从下往上贪，贪到必须放的时候再放，这样可以做到每个公园在保证这个子树被覆盖的同时，覆盖尽可能多的其他点
可以发现，需要维护的值有：
$reach_u$，表示最远的没有被覆盖的点的距离，一旦这个值将要超过二分的 $val$，这个点就必须要放了
$dis_u$，表示子树内最近的公园距离它的距离，离这个点距离不超过 $val-dis_u$ 的点就可以不需要考虑
这个贪心有一个问题是，因为公园会对子树外的点有影响，应该按照什么顺序遍历子树，才能保证答案正确性，或者是证明这个顺序对答案没有影响
分类讨论一下可以发现，一个子树内放了公园导致另一个子树内的公园不用放了，这种情况是不存在的
也可以说是，这部分的影响只会减少它的祖先上放的公园的数量，而对它的兄弟没有影响
贪心的正确性得到证明，$O(n\log n)$
笛卡尔树上一个点的子树是一个区间，对应以这个点为最大值的极长子段，这个性质很好证明
因此只需要维护每个点左边的第一个比它大的数 $l_i$，右边第一个比它大的数 $r_i$，答案就是 $\sum r_i-l_i-1$
由于是从小到大加入，因此加入位置 $i$，相当于 $r_{1\sim i-1}$ 对 $i$ 取 $\min$，$l_{i+1\sim n}$ 区间 $+1$ 后对 $val_i$ 取 $\max$，这个用 $\text{Segment Tree Beats}$ 就可以解决
瓶颈在 $\text{Segment Tree Beats}$，$O(n\log n)$
大力树剖，线段树上维护区间颜色段数量和两端点颜色，合并的时候看一下合并的两个点颜色是否相同即可，$O(n\log^2n)$
对于一个点 $u$，如果它的一个儿子的权值和 $2sz_v\ge \sum val_u$，那么重心必定在 $v$ 的子树中，而最终重心就是从根开始跳，跳到没法跳的那个点
因此也可以注意到，这条路径是树上的一条链，重心就是这条链上最深的那个点
直接大力上树剖，由于任意一条链的 $dfn$ 序递增，则可以直接在线段树上二分找到重心，现在问题是如何计算答案
令重心为 $u$，答案其实就是 $\sum val_v(dis_u+dis_v-2dis_{\operatorname{lca}(u,v)})$，显然拆开算，前两个只需要维护 $\sum val$ 和 $\sum dis\times val$ 就好
问题在第三个如何解决，注意到根到 $\operatorname{lca}(u,v)$ 的路径必定同时被根到 $u$ 和根到 $v$ 两条路径覆盖到
尝试把信息拆开放在根到 $v$ 的路径上，再去查询根到 $u$，于是只需要维护 $\sum sz\times w_{fa}$，其中 $w_{fa}$ 表示一个点到其父亲的边权
总共是 $O(n\log^2 n)$，实现可能有点烦？
由于每次增加的边权只会是 $1$，因此最短路的变化不超过 $c$，考虑维护差值
自然想到 $\text{Johnson}$ 算法中关于重新计算边权的方法，重定义边权后，新图的最短路就是最短路的差值
由于变化不超过 $c$，因此所有距离超过 $c$ 的都不可能成为答案，不进行拓展，又因为 $c$ 很小，所以求最短路的过程中直接开个桶代替原来的堆
少掉一个 $\log$，变为 $O(qn)$，时限 $10s$，可以通过
显然求的就是这个点集的割点数量，建出圆方树，只需要计算包含这个点集的最小子图上的圆点个数即可
套路性地，把点集按照 $dfs$ 序排序，答案就是相邻两点间的路径经过的圆点的总和的一半
这个东西还是不好算，好算的是距离，把圆点的权值往上放到方圆边上，这样求的就是两点间的距离
需要注意的是如果深度最浅的点是圆点，它的贡献还没算上，$O(q\log n)$