网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P10930
2024-08-30
P3320 [SDOI2015] 寻宝游戏 与 P10930 异象石 与 CF176E Archaeology
思路:考虑按照dfn序将关键点的集合排序后为\(a_0,a_1,\cdots,a_k\),则答案为:\[\frac{\sum\limits_{i=0}^k\operatorname{dis}(a_i,a_{(i+1)\bmodk})}{2}\]简单证明一下:需要找出包含一些关键点的最小联通导出子图。则随便以一个关键点为根,对于子树内没有关键点的子树直接