山东没掉了。赛后乱做了一下。
难度评价是比之前偏简单。只要联想到一些算法就变成常规题了。
T1 T2 是常规联赛前两题难度，T3 如果哈希做法的话不好评价（毕竟之前做到的 CF 随机哈希题都 *2800 了），T4 估计就是省选 D1T1-D2T1 难度。
总体来说，有概率阿克。
T1
题意：有不保证连通无向图，起点和终点都是1，要求钦定四个点 \(a,b,c,d\) 使得 \(dis(1,a),dis(a,b),dis(b,c),dis(c,d),dis(d,1) \le k+1\) 并最大化 \(v_a+v_b+v_c+v_d\)，求最大值。
简单题。考虑枚举每个点 \(u\) 跑 01bfs 求出距离，然后枚举另一个点 \(v\) 使得 \(dis(v,1),dis(u,v)\le k+1\)，这时的点对 \((u,v)\) 可以当成 \(a,b\) 或者 \(c,d\)。
所以预处理完了之后枚举两个这样的点对 \((u_1,v_1),(u_2,v_2)\)，使得 \(dis(u_1,u_2)\le k+1\) 然后取个最大值即可。不难发现这样是 \(n^4\) 的，但是你可以对于每个 \(u\) 先求出最大值点对 \((u,v)\)，然后用这样的点对去更新答案。但是有个小问题，就是这几个点可能重复，所以你只需要存前三个大值然后暴力枚举判断合法性即可。复杂度 \(O(9n^2)\)。
T2
题意不写了。
更简单题。但是要码点东西。
考虑当 \(a\) 选负数的时候，\(b\) 一定取最大值，\(a\) 选正数的时候，\(b\) 一定取最小值。
所以你维护 \(a\) 的正/负数绝对值最小/大和 \(b\) 的最大最小值的 st 表即可求答案。
稍微分类讨论下即可。
T3
题意：有向图，定义图是好的当且仅当每个点出度恰好为一，要求支持若干次操作，每次可以删掉一个点所有入边，删掉一个点所有出边，加上一条目前没有的原图边，删掉一条目前有的边，每次操作完判断图是不是好的。
数据都是 \(5\times 10^5\)。
考虑这玩意很强，不好做，考虑乱搞。
那么你只要想到随机哈希本题就差不多变成弱智题了。
给每个点随机一个权值，然后对于一条边，它的权值就是出点的权值，每一条边的权值在他的入点上计算。那么当所有现存边的权值恰等于所有点权和的时候，我们可以认为他合法。动态维护边权很好维护。对于每个点维护原图中所有入边权值和，目前所有入边权值和即可。
对于点操作，直接将这个点目前的入边权值置为 0 或者原图入边权值和，边操作直接加减即可。
我怕冲突，总共做了十次判断，都合法答案才合法。
实际上做一次基本就一定是对的了。
T4
也不太难。先考虑暴力 dp，对于一个点维护走到这个点距离 \(0,1,...,k-1\) 的最小代价，然后转移到他的父亲，对于路径两端分别做到 LCA，其中一个做到父亲是 LCA 即可。然后将这两个答案合并起来就是答案。
发现转移是矩阵形式，联想到 DDP 的矩阵维护，于是你用矩阵维护转移然后倍增预处理即可。
实际上带修就变成了几乎完全的 DDP 板子，不带修就只用倍增了。
手玩出矩阵然后实现就很简单了。
标签：Submission,枚举,即可,2022,权值,入边,CSP,dis From： https://www.cnblogs.com/infinities/p/16843415.html