文件名称：拓展总结-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:39
集训队论文集
8.2 拓展总结 圆方树可以非常高效、简洁、通用地处理仙人掌上的问题，同样也可以解决一般图上 的一些询问简单路径的题目；链分治可以解决一类支持修改的、以子树为状态的 DP问题， 还能结合 LCT以支持 Link/Cut及任意子树询问。使用轻重链剖分来维护圆方树，可以高效 地解决了一类支持单点修改的两点之间简单路径询问的问题。 如今，点双连通分量和支持修改的 DP 问题，对很多选手来说都具有一定的难度。我 希望这道题能引发选手对链分治在树上带修改 DP 问题中的应用及圆方树的一些思考，能 够有更多的扩展，解决更加广泛的问题。如果有同学在此方面的研究有所收获，欢迎来找 我讨论。 9 致谢 1. 感谢中国计算机学会提供学习与交流的平台。 2. 感谢父母的养育之恩。 3. 感谢福州一中的陈颖老师的关心与教导。 4. 感谢福州一中的各位学长带给我的启发和指导。 5. 感谢国家集训队教练们带给我的帮助。 6. 感谢福州一中的刘一凡同学在我研究圆方树给予我巨大的帮助，并为圆方树命名。 7. 感谢钟知闲同学为本题验题、为本文审稿。 8. 感谢其他所有本文所参考过的资料的提供者。 9. 感谢各位在百忙之中抽出宝贵的时间阅读。 73