APIO 2020 补题记录

[[APIO2020]粉刷墙壁](https://www.luogu.com.cn/problem/P6764) 如果这道哪几个左端点开始可以刷，那么贪心即可。 考虑 dp，$f(i,j)$ 表示 $i$ 作为左端点，$i$ 颜色匹配 $j$ 号承包商，最大长度。复杂度 $O(nm)$ 每种颜色只转移能刷的承包商，滚动数组一下就可以AC了（ [[APIO2020]交换城市](https://www.luogu.com.cn/problem/P6765) 图上不好处理。于是从小到大建 kruskal 重构树，需要统计经过 $u$ 的三岔路 & 带环路径的最小值 考虑树形 dp，设 $f(u)$ 表示经过 $u$ 的最小带环路径，$g(u)$ 表示经过 $u$ 的最小三岔路。 $f:$ 考虑延伸到儿子，延伸到祖先，一条非树边 $g:$ 考虑延伸到儿子，延伸到祖先，自己伸出的 3 条树边 [[APIO2020]有趣的旅途](https://www.luogu.com.cn/problem/P6766) 题目中支持的是询问 dist 和 size 如果找到重心 $rt$ ，并且 $rt$ 有 2 个儿子，那在 2 个儿子里跳来跳去即可构造 如果 $rt$ 有 3 个儿子，那就从一个 dep 最大点开始，找另两个儿子中 dep 最大的，然后跳过去。 写起来比较烦。。