把字典树建出来，问题就转化成要选择m个节点，使得它们能覆盖所有叶子节点，且不存在两个节点使得一个是另一个的祖先。
于是可以在字典树上跑树形dp，复杂度 \(O(n^2m)\) 或 \(O(nm^2)\) ，后者稳过，前者常数小的话可以通过本题。
还有一种思路，就是把树用dfs序拍扁，然后就变成了线性结构上的区间覆盖问题。然而空间开不下（ \(O(n^2m)\) ）。考虑所有区间的右端点一定在一个叶子节点上，那么可以压缩一下空间（ \(O(nm)\) ）。
\(O(\text{可以通过}20\%\text{的数据})\)
这是一个约瑟夫环。
先对点进行极角排序，然后如果你会 \(O(n)\) 约瑟夫环的话可以做到 \(O(n^2\log n)\) 或 \(O(n^2)\) ，可以通过 \(30\%\) 的数据。
三岁神仙\(\text{Q}\color{red}{\text{iyang}}\)秒了此题
转载于:https://www.cnblogs.com/BlogOfchc1234567890/p/11622858.html
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
