T1
容易想到枚举 \(B,C\)，然后 \(A,D\) 可以预处理，即对于 \(i\) 处理存在路径 \(1\rightarrow j\rightarrow i\) 中 \(j\) 的权值最大的，那么只需枚举 \(B,C\) 然后分别取最大的 \(A,D\)。但是因为此时最大的 \(A\) 可能与 \(C,D\) 重复，所以需要保存前三大的 \(j\) 才能保证找到最大的合法路径。接下来为了避免分类讨论，可以枚举前三大的组合，判断是否合法并更新 \(\max\) 即可。
T2
注意到两人选择的只可能是正负的 \(\max,\min\) 或是 \(0\)，为了避免分讨，直接对每个数组开五个 \(ST\) 然后暴力找到这些数，然后 \(5*5\) 的枚举选的方法即可，实现比较优美，开一个 \(ST\) 的结构体，再开一个数组的结构体。
T3
删加一条边或某个点的所有入边，判断当前图是否是内向基环树森林。
只需要判断每个点的出度是否都是 \(1\)，那么由于每个点的出度都是 \(1\)，就有一种随机化 hash 的做法。
具体来说，每个点有一个随机权值 \(a\)，每个点在当前图中的权值 \(b\) 是所有入边的点的 \(a\) 之和。那么如果所有点 \(b\) 的和等于所有点 \(a\) 的和，就有较大概率当前图满足条件。
T4
给出一棵树，一个点一次可以跳到距离小于等于 \(k\) 的所有点，一条路径权值是跳的所有点点权之和，求树上两点间路径的最小权值。
逐步递进，\(k=1\) 时，就是树上两点距离，\(k=2\) 时，注意到假如跳出了两点间的链，那么跳回来的点在跳出去之前一定可以跳到，所以不会跳出链，\(k=3\) 时，同上，不会跳出去两个点，也就是如果跳出链，只会跳到链周围一圈，而对于一个点，它周围一圈没有区别，所以可以找到一个点周围的 \(\min\) 记作 \(ex[u]\)。
那么假设把这条链找出来了，设 \(dp[u][0/1/2]\) 表示上个跳到的点与 \(u\) 的距离为 \(0/1/2\)，然后你发现就可以用 \(dp[u-1]\) 更新 \(dp[u]\) 了。
- \(dp[u][0]=\min\limits_{j=0}^k(dp[u-1][j]+a[u])\)
- \(dp[u][1]=\min(dp[u-1][0],[k=3](dp[u-1][1]+ex[u]))\)
- \(dp[u][2]=[k\ge2]dp[u-1][1]\)
发现是线性转移，而 \(+\) 对 \(\min\) 有分配律所以可以用矩阵优化转移，可以用倍增维护一个向上和向下的矩阵乘，也可以树剖。
标签：CSPS2022,min,题解,可以,路径,枚举,权值,dp From： https://www.cnblogs.com/llmmkk/p/16843759.html