T1. 假期计划

枚举 B, C 就行，预处理前三大的 A / D。时间复杂度 O(nm+n2)O(nm + n^2)。

T2. 策略游戏

按照 B 中是否有正负数分讨即可。

T3. 星战

判断的条件就是每个点出度都为 11。

给每个点随机一个权值 vali\text{val}_i，对于每个点 vv 维护 sv=∑(u,v)∈Evalus_v = \sum_{(u, v) \in E} \text{val}_u，并维护 ∑sv\sum s_v。每次检查 ∑sv\sum s_v 是否等于 ∑vali\sum \text{val}_i 即可。

感觉不稳的话就多随几次。

T4. 数据传输

k=2k = 2 的时候中途的点不会跳出 sis_i 到 tit_i 的链上。矩乘加速是显然的。

k=3k = 3 的时候中途的点可能会跳出 sis_i 到 tit_i 的链上，但是可以发现出去的点一定是这条链某个点的邻居。进一步可以发现，这个点一定是链上某个点所有邻居中点权最小的那个。

还是考虑矩乘加速，先写出朴素转移。设 fif_i 表示跳到链上第 ii 个点的最小时间，gig_i 表示跳到链上第 ii 个点的邻居的最小时间。记 aia_i 表示链上第 ii 个点的点权，bib_i 表示链上第 ii 个点的所有邻居中点权的最小值。

f(i)=min⁡{min⁡j=i−Ki−1{f(j)},min⁡j=i−K+1i−1{g(j)}}+aig(i)=min⁡{min⁡j=i−K−1i−1{f(j)},min⁡j=i−K+2i−1{g(j)}}+bi\begin{aligned} f(i) &= \min\left\{\min_{j = i - K} ^ {i - 1}\{f(j)\}, \min_{j = i - K + 1} ^ {i - 1}\{g(j)\}\right\} + a_i \\ g(i) &= \min\left\{\min_{j = i - K - 1} ^ {i - 1}\{f(j)\}, \min_{j = i - K + 2} ^ {i - 1}\{g(j)\}\right\} + b_i \end{aligned}

矩阵加速如：

[+∞0+∞+∞+∞+∞+∞0+∞+∞aiaiaiaiai+∞+∞+∞+∞0+∞bibi+∞bi]⋅[f(i−3)f(i−2)f(i−1)g(i−2)g(i−1)]=[f(i−2)f(i−1)f(i)g(i−1)g(i)]\begin{bmatrix} +\infty & 0 & +\infty & +\infty & +\infty \\ +\infty & +\infty & 0 & +\infty & +\infty \\ a_i & a_i & a_i & a_i & a_i \\ +\infty & +\infty & +\infty & +\infty & 0 \\ +\infty & b_i & b_i & +\infty & b_i \end{bmatrix} \cdot \begin{bmatrix} f(i - 3) \\ f(i - 2) \\ f(i - 1) \\ g(i - 2) \\ g(i - 1) \end{bmatrix} = \begin{bmatrix} f(i - 2) \\ f(i - 1) \\ f(i) \\ g(i - 1) \\ g(i) \end{bmatrix}

注意下乘法的顺序，以及 LCA 是否被计算到或算重。