2025.11 做题记录

洛谷P4172 [WC2006] 水管局长
如果没有删边操作，那么就是把图的 mst 拉出来，每次查询路径最大值。
如果有删边，先倒过来变成加边。
每次加边就暴力维护 mst 形态。若当前加的是 \((u,v,w)\)，如果 \(u,v\) 不在一个连通块就直接加，否则若 \(u,v\) 路径最大值大于 \(w\)，就把最大值那条边删了，加上 \((u,v,w)\)。然后 \(O(n)\) 扫一遍树维护一些信息就行了。
可以用邪恶斜二倍增做 \(O(n)-O(\log n)\) 路径最大值或查询 lca，也很好写。记删边次数为 \(c\)，那么时间复杂度就是 \(O((m-c)\log(m-c)+nc+q\log n+c\log n)\)，显然能过。那个 \(O(c\log n)\) 是维护删边的复杂度。
洛谷P5405 [CTS2019] 氪金手游
把 \(u_i\) 到 \(v_i\) 的有向边连上，那么把有向边看成无向边后是棵树。
同时有叶向边和根向边比较难做，可以先想只有叶向边怎么做。
显然每一个点出现的时间都比它子树内的点早。假设 \(w_i\) 固定，记 \(s_i\) 表示 \(i\) 子树内 \(w\) 的和，\(S\) 表示 \(w\) 的全局和，那么点 \(i\) 满足这个条件的概率就是 \(\frac{w_i}{S}\sum\limits_{j=0}^{\infty}(\frac{S-s_i}{S})^j=\frac{w_i}{s_i}\)，答案就是这个的积。
可以发现 \(\frac{w_i}{s_i}\) 只和子树内的点有关，考虑 dp。记 \(f_{u,i}\) 表示只考虑 \(u\) 子树，\(s_u=i\) 且合法的概率，转移是一个树形背包。
如果有根向边也是简单的，把根向边容斥掉变成叶向边，转移的时候乘一下容斥系数就行，显然系数是 \(-1\)。
CF2121H Ice Baby
显然有一个 \(O(n^2)\) dp。设 \(f_i\) 表示目前长度为 \(i\) 的所有不降子序列中最后一个数的最小值，显然 \(f\) 单调不减。
转移就是对所有的 \(j\) 满足 \(l_i\le f_j\le r_i,f_{j+1}=f_{j}\)，然后改一个 \(l_i\) 到最小的 \(j\) 那里，可以用 multiset 维护（神奇。
具体是每次转移找到最大的 \(j\)，把 \(f_{j+1}\) 删了，然后 emplace 一个 \(l_i\)。
洛谷P10525 [XJTUPC 2024] 图上操作
对于怎么求这个最短路，可以从大到小枚举边权，把当前边权的边都加进去，如果 \(u\) 是新的能从 \(1\) 走到的点，那么 \(ans_u\) 就是当前边权。
因此可以维护 \(O(V)\) 个图，第 \(i\) 个图包含了边权大于等于 \(i\) 的所有边，对每个图都维护 \(1\) 能走到的点，每次操作相当于删边和加边。
对于加边，如果加的是 \(u\to v\)，且当前 \(1\) 能走到 \(v\)，就从 \(v\) 开始搜，拓展一下新点，同时维护答案。
发现删边比较难做，离线下来倒着做就行。
洛谷P14362 [CSP-S 2025] 道路修复 / road
首先注意到原图边只有 mst 上的边有用，边数就优化到 \(n-1\) 条了。
\(k\) 这么小一看就是只能 \(2^k\) 枚举的。每次枚举，把乡村边排序，和 mst 边归并一下，做个 kruskal 就行，记得用 \(O(\alpha(n))\) 的并查集。
大概算一下时间复杂度，具体是啥我不知道反正过不了。每次都排个序太慢了，还带个 \(\log\)，可以归并处理。
然后就做完了，算一下空间发现会爆，可以存边的时候端点用 short，但是这个做法比较难写我就不写了（）
qoj8055 Balance
vp 时想出来了，但没写完。。。
可以发现，边双内的点颜色相同，不然会炸，缩起来后就变成了一棵树。
可以发现，最后是 \(c-1\) 条边把树分割开，每个联通块都是同一种颜色，且一条边连的颜色要相邻。
然后呢，处理出一个一个点的子树里能不能装下前 \(i\) 种颜色或后 \(j\) 种颜色就行，可以发现每个点对应的 \(i\) 或 \(j\) 最多就一个。
最后呢，在根节点合并一下就可以了。
最后的最后呢，还要把这一坨写出来。
qoj9265 You Are Given a Tree
模拟赛的题，感觉很典。
计算所有非根的点 \(u\) 上面那条边的贡献，显然一个区间能贡献当且仅当 \(u\) 下面和上面都有区间内的点。容斥一下，看成全部都在 \(u\) 下面或全部都在 \(u\) 上面的区间个数。
这个怎么做呢？对每个点开一个大小为 \(n\) 的数组，如果 \(v\) 在 \(u\) 子树里 \(f_{u,v}\) 就是 \(1\) 否则是 \(0\)，区间有贡献当且仅当在一个颜色连续段里，可以用 set 启发式合并维护一下 \(1\) 的极长连续段。
ARC189D Takahashi is Slime
简单题。
先建大根笛卡尔树，一个点能吞掉子树内的所有点，如果吞了后能吞父亲就往上跳。
这不对啊，一个点能吞的是小于而不是大于，只需要对儿子分讨就可以了。
qoj14504 挑战图同构
简单题。
注意到联通的 \(u,v\) 合法当且仅当在两个图的最小生成森林上路径最大值相等。
这个还是不好维护。换个思路，对于所有边权 \(w\)，在两个森林上以它为路径最大值的点对集合相等。
这个就好做了。从小到大加边，用并查集维护一下哈希。
ABC282Ex Min + Sum
一开始想的是笛卡尔树，想了好久没想出来（
先给 \(b\) 做个前缀和，记为 \(c_i\)。枚举右端点，记 \(d_i=\min\limits_{j=i}^{r}a_j\)，区间合法就是 \(c_r-c_{l-1}+d_l\le S\)。
用 \(e_i\) 表示 \(d_i-c_{i-1}\)，那么要求的就是 \(e_i\le S-c_r\) 的个数。
\(d_i\) 可以每次右端点右移的时候用单调栈维护一下，现在要支持区间加、前缀查询小于等于某个数的个数，可以分块+二分做到 \(O(n\sqrt n\log n)\)，应该能过？
看了题解后发现笛卡尔树也能做（
就是把小根笛卡尔树建出来，要支持查询 \(ql\le l\le u\le r\le qr\)，\(c_r-c_{l-1}\le S\) 的个数。建主席树，枚举一下其中一个端点，算另一个端点的个数就行。枚举的时候枚举少的那一边，复杂度是对的。
CF2152F Triple Attack
选上的前两个肯定是 \(l\) 和 \(l+1\)，如果不是的话调到这两个肯定不劣。
然后就是维护两个点 \(x\) 和 \(y\)，初始时 \(x=l,y=l+1\)，每次让在左边的那个点往右跳到第一个超过 \(z\) 的位置，如果超过 \(r\) 就结束了，问次数。
可以发现对于一个点，它跳的时候不会被另一个端点影响，因为跳之后肯定就超过去了，可以对每个 \(i\) 找到第一个距离它超过 \(z\) 的位置 \(p_i\)，如果没有就让 \(p_i=n+1\)。连 \((i,p_i)\) 后会形成一个根为 \(n+1\) 的树，每次要查询从一个点开始最多跳多少次父亲小于等于 \(r\)，直接倍增就完了。
跳的时候可能会跳到同一个点，直接换到下一个点继续跳就行。
CF1188C Array Beauty
直接算有点困难，可以枚举 \(d\)，求出美丽值至少为 \(d\) 的方案数。
先排个序。设 \(dp_{i,j}\) 表示考虑了前 \(i\) 个数，选了 \(j\) 个，前缀和优化可以做到 \(O(nk)\)。
很难（？注意到答案最大是 \(\frac{V}{k}\)，因此总复杂度为 \(O(nV)\)。
洛谷P7967 [COCI 2021/2022 #2] Magneti
将 \(r_i\) 减 \(1\)！！！！！！！！！！
仔细读题，磁铁 \(i\) 和 \(j\) 能互相吸引的条件是距离小于等于 \(\max(r_i,r_j)\)。
假设磁铁的顺序固定，记它的直径 \(L=n+\sum\limits_{i=1}^{n-1}\max(r_i,r_{i+1})\)，根据插板法可以得到按顺序插进 \(l\) 个位置的方案数是 \(\binom{l-L+n}{n}\)。
这个东西不是很好做，看上去就是要 dp 的。先按 \(r_i\) 从小到大排序，把 \(\max\) 去掉，设 \(f_{i,j,k}\) 表示考虑了前 \(i\) 个磁铁，分成 \(j\) 组，直径的和为 \(k\) 的方案数。
转移：
第 \(i\) 个磁铁新开一个组，有 \(f_{i,j,k}\gets f_{i-1,j-1,k-1}\)。
第 \(i\) 个磁铁插到某个组的两边，有 \(f_{i,j,k}\gets f_{i-1,j,k-r_i-1}\times 2\times j\)。
合并两个段，然后第 \(i\) 个磁铁插到中间，有 \(f_{i,j,k}\gets f_{i-1,j+1,k-2\times r_i-1}\times j\times (j+1)\)。
答案就是 \(\sum\limits_{L=1}^{l}f_{n,1,L}\times\binom{l-L+n}{n}\)。