隔了好久好久。。。
T1
题意：给定 $n$ 个点 $m$ 条边的无向图，每个点上有权值 $v_i$，现在从点 $1$ 走到另外 $4$ 个点再返回点 $1$，要求另外点与点之间的路程需小于等于 $k+1$，求另外四个点的权值和最大值。$n\le 2500,m\le 10000$。
乱搞，考虑处理出每个点在 $k+1$ 步内能到达的所有点，以及这些点中的最大值，亚大值，次大值。然后枚举中间两个点即可。时间复杂度 $\mathcal O(nm+n^2)$。
T2
题意：给定两个长度分别为 $n,m$ 数组 $A,B$，有 $q$ 次询问 $l_1,r_1,l_2,r_2$，表示在小 L 先在数组 $A$ 的 $[l_1,r_1]$ 中选一个数 $a_x$，小 Q 再在数组 $B$ 的 $[l_2,r_2]$ 中选一个数 $b_y$，每一轮的得分为 $a_x\times b_y$ 。小 L 想使得分最大，小 Q 想使其最小。两人都是足够聪明的玩家，每次都会采用最优的策略。求得分是多少。$n,m,q\le 10^5$。
注意到是小 L 先选，小 Q 后选，很容易根据正负关系分类讨论，接着用 ST 表或者线段树维护即可，此处不再赘述。时间复杂度 $\mathcal O(n\log n+q\log n)$，此处视 $n,m$ 同阶。
T3
题意：给定 $n$ 个点 $m$ 条边的有向图，有 $q$ 次操作，操作有 $4$ 种类型：1.禁用边 $(u,v)$；2.禁用 $u$ 所有的入边；3.激活边 $(u,v)$；4.激活 $u$ 所有的入边。要求判断每次操作后的图是否为一棵基环树。
判断基环树即为判断每个点是否有且仅有一条出边。显然合法的入边总数应当为 $n$，即满足 $\displaystyle \sum_{i=1}^n in_i=n$。但是这样显然很大可能有多组解。于是尝试 Hash 一下。
尝试赋给每个点一个随机权值 $v_i$，并且使 $\displaystyle in_i=\sum_{(j,i)\in E} v_j$，现在我们只需要判断其是否满足 $\displaystyle \sum_{i=1}^{n} in_i=\sum_{i=1}^n k_i v_i=\sum_{i=1}^{n} v_i$。因为这个方程极大可能只有一组解 $k_1=1,k_2=1\dots k_n=1$。并且对于修改操作，我们只需要简单维护 $in_i$ 即可。时间复杂度 $\mathcal O(n+q)$。
T4
题意：给定一棵 $n$ 个节点的树，每个点上有权值 $v_i$。给定常数 $k$，有 $q$ 次询问 $u,v$，对于一条路径 $p_1\to \dots \to p_w,p_1=u,p_w=v$，需要满足 $\forall dis(p_i,p_{i+1})\le k$，路径的权值为 $\displaystyle \sum_{i=1}^w v_i$，询问最小的权值为多少。$n,q\le 2\times 10^5,k\le 3$。
先考虑 $k=1,2$ 的情况。$k=1$ 时，直接输出 $u\to v$ 上所有点的权值和即可，倍增处理。$k=2$ 时，我们发现路径 $p_1\to \dots \to p_w$ 依然是在 $u\to v $ 上的，但并不是所有点都要取。设计 $(x,t)$ 表示到 $x$ 已经走了多少步没有选点。还是考虑倍增处理，设计倍增数组 $f_{x,k,p,q}$ 表示从 $(x,p)$ 到 $(fa_{x,k},q)$ 最小权值和，这是容易预处理以及计算的。
有了 $k=1,2$ 的启发，我们还是尝试倍增。我们发现完全可以沿用 $k=2$ 中倍增数组 $f_{x,k,p,q}$ 的设计。但是需要考虑的是，现在是可以走到 $u\to v$ 之外的点的。但是简单观察发现，是只可能绕过 $u\to v$ 上某个点，转而去到与之相邻的 $v_i$ 最小的点上，再回到 $u\to v$ 上。那么现在 $f_{x,k,p,q}$ 也是容易预处理的了。
但需要注意的是计算时，将 $u\to \text{LCA}$ 与 $\text{LCA}\to v$ 拼在一起时的两种特殊情况：1.若 $p=0,q=0$，则 $v_{\text{LCA}}$ 会被计算两次，需要减去。2.若 $p=2,q=2$，则 $v_{\text{LCA}}$ 被少算，需要加上。
时间复杂度 $\mathcal O(n\log n+q\log n)$。