APIO 2020 补题记录

· · 个人记录

[APIO2020]粉刷墙壁

如果这道哪几个左端点开始可以刷，那么贪心即可。

考虑 dp，f(i,j) 表示 i 作为左端点，i 颜色匹配 j 号承包商，最大长度。复杂度 O(nm)

每种颜色只转移能刷的承包商，滚动数组一下就可以AC了（

[APIO2020]交换城市

图上不好处理。于是从小到大建 kruskal 重构树，需要统计经过 u 的三岔路 & 带环路径的最小值

考虑树形 dp，设 f(u) 表示经过 u 的最小带环路径，g(u) 表示经过 u 的最小三岔路。

$g:$ 考虑延伸到儿子，延伸到祖先，自己伸出的 3 条树边 [[APIO2020]有趣的旅途](https://www.luogu.com.cn/problem/P6766) 题目中支持的是询问 dist 和 size 如果找到重心 $rt$ ，并且 $rt$ 有 2 个儿子，那在 2 个儿子里跳来跳去即可构造 如果 $rt$ 有 3 个儿子，那就从一个 dep 最大点开始，找另两个儿子中 dep 最大的，然后跳过去。 写起来比较烦。。