2023.4 做题记录
[NOIP2018 提高组] 旅行
看到题目中要求 \(m=n\) 或 \(m=n-1\)，此时就应当分类讨论。
① 当 \(m=n-1\) 时：
此时数据为一颗树。
我们贪心的想：起始点为 \(1\) 的时候显然最优。对于每一个节点，在它子树内按照从小到大的顺序遍历显然最优。
复杂度 \(O(n \log n)\)，瓶颈在于排序。因此可以将快速排序换为其他排序达到 \(O(n)\) 的效果，然而并没有这个必要。
② 当 \(m=n\) 时：
此时数据为一颗基环树。
\(O(n^2)\) 做法：
我们先找出环，然后考虑枚举这个环上的一条边，将这条边删去后就与情况 ① 相同。而此时枚举完所有边，将答案取最小即可。
复杂度 \(O(n^2)\)。可以通过原数据，但有更优的做法。
\(O(n \log n)\) 做法：
我们考虑，本题的关键在于：当走到一个环上的时候，从哪一个点 \(p\) 回溯？因为当我们从 \(p\) 回溯，相当于删掉了 \(p\to to_p\) 这条边。如果能解决这个问题，就可以保证在一次 DFS 内求出答案。
考虑什么时候回溯。首先想到的是当走下一个节点不如回溯之后走到的第一个节点，那么必然要回溯。但是这并不一定。如果这个节点不是父亲节点所有出点中最大的，那么回溯之后要走一个比当前点还要大的点，显然更劣。
因此，回溯的条件是：当这个节点是父亲节点所有出点中最大的，并且还要大于回溯后走到的第一个节点。
具体实现可以记录回溯后走到的第一个节点，记录是否回溯来实现。
复杂度 \(O(n\log n)\)，瓶颈仍然在于排序。
[IOI2008] Island
首先，观察题目以及样例，发现有些玄妙。我们先不管船，单独看桥会发现一个联通块内的答案就是树的直径。然后来看船，显然对于任意一个联通块内的节点都不能使用船，因此船只能用于两个联通块之间的交通，并且每个联通块只能走一遍。
再次观察题目会发现边数等于点数，即整个图是基环树森林，于是最后这道题就可以转化为：
给出几颗基环树，求出其直径之和。
其实这是一道板子，不过可以写一下。
考虑环形 dp 处理方式，首先对于一颗基环树，看做一个环上挂着一些树。对于子树内求出最长链的长度，然后作为环上这个点的点权；现在我门有点权 \(p\) 和边权 \(w\)，那么要选出两个点 \(u,v\)，满足 \(p_u+p_v+dis(u,v)\) 最大。
此时这个式子要在环上 dp，这时考虑朴素的处理方式——断环为链。此时在设 \(dp(i)\) 表示第二个节点选在 \(i\) 的值，那么方程就是：
\[dp(i)=\max_{i-cnt+1\le j \le i-1}\{p_i+p_j+dis(i,j)\} \]其中 \(cnt\) 为环上节点数量。发现 \(dis(i,j)\) 可以 \(O(n)\) 前缀和求出，然而暴力枚举这个式子的复杂度仍然是 \(O(n^2)\)。
发现取 \(\max\) 的范围是一段长度固定的区间，自然想到单调队列优化 dp。令 \(sw_i\) 为边权前缀和，式子可以化为 \(dp(i)=\max_{i-cnt+1\le j \le i-1}\{p_j-sw_j\}+p_i+sw_i\)。维护 \(p_j-sw_j\) 即可。
最后取 dp 最大值，然后累加答案即可。
剩下的还要注意很多细节：
- 基环树的直径可能就是一颗子树的直径，因此在 dp 过程中还可以记录次长链直接求出子树直径。
- 边权有 \(10^8\)，因此要开
long long。 - 单调队列优化 dp 的时候注意赋初始值。