2024.2 做题记录

省流：因为一月底回厦门玩然后又回泉州过年，直到 2.17 才开始做题。

[APIO2018] 铁人两项

圆方树和后缀数组我都想开个贴单独写。考虑关于“简单路径”，在点双上都有很特殊的性质。考虑把原图的圆方树建出来，然后考虑简单路径和圆方树的关系。

注意到，在同一点双的两点的简单路径的并集，恰好为整个点双，也就是说，对于两圆点在树上的路径中方点的相邻原点的并集也就是两点间所有简单路径经过点的并集。

枚举起点终点 \(s, f\)，合法中间点 \(c\) 的数量为并集 \(-2\)（去掉起点和终点）。那么计算答案就好计算了，我们给方点赋值为相邻圆点数量，圆点赋值为 \(-1\)，问题转化为两点路径权值和。

为什么这样是对的？
按照刚刚的赋值方式，我们在经过一个点双时会正好把点双的大小 \(-2\) 算进去，\(-1+sz_u-1\)。但是因为在圆方树中任意圆点相邻的都是方点，而又因为是路径，所以一个圆点又会被两个方点贡献，那么贡献又回到了 \(1\)。
但是起点和终点不会被两个方点相邻，所以它们的贡献也确实就是 \(-1\)，那么总的贡献就正确了。

现在复杂度是 \(O(n^2)\)，怎么办？

转化思路，我们统计每个点的贡献，这是好做的，dp 就是一个乘法原理，注意只能统计圆点的贡献方案。

Tourists

套路的变成圆方树，那么也可以把所有相邻原点的权取 \(\min\) 挂到方点上，直接查询路径最小值即可。

考虑修改，这样做要把该圆点所有相邻的方点做出修改，于是我们对于每个方点改为只记录其儿子的贡献，这样用树剖和线段树就可以维护了，同时对于每个方点维护一个 multiset。维护指定值删除和最小值。

https://www.luogu.com.cn/discuss/780218

Count on a tree

不太难。因为主席树天生是一个支持前缀和的东西，所以我们直接像记录树上前缀和一样，把链从上至下当作是序列，然后对于主席树上也有的差分，有

作为查询版本，之后直接主席树二分即可。我倒是觉得这个式子没什么好解释的。

压力

这题太纯了，直接秒了，做也是一遍过。因为一个点能成为割点一定是“所有简单路径必须经过的点”，也跟圆方树很有关系，于是考虑建出原图的圆方树。不难发现，一条路径上涉及到的所有的圆点都是必须经过的，直接树上差分即可。

我确实觉得这是个很直觉的东西，不过我还是应该感性写一下理解。
如果我们经过某个方点控制的圆点，然后走出了这个点双，也就是说下一步的点就不属于当前点双了（如果有多条路径当前点双就不是极大点双），那也就是说这是唯一路径，也就是说这是割点。
证毕。

[JSOI2007] 字符加密

最秒的一集，首先断环成链肯定是有必要的，然后发现直接后缀数组就是题目里要的东西，就通关了。

[SDOI2016] 生成魔咒

待续，睡觉了。