题意简述： 一棵 n 个节点的树，边有边权。 每个点可能是关键点，每次操作改变一个点是否是关键点。 求所有关键点形成的极小连通子树的边权和的两倍。 题解： 有一个结论：DFS 序求出后，假设关键点按照 DFS 序排序后是 a1 ,a2 ,…,ak 。{a 1 ,a 2 ,…,a k }。 a1 ,a2 ,…,ak 。 那么所有关键点形成的极小连通子树的边权和的两倍等于 dist(a1 ,a2 )+dist(a2 ,a3 )+⋯+dist(ak−1 ,ak )+dist(ak ,a1 )。dist(a 1 ,a 2 )+dist(a 2 ,a 3 )+⋯+dist(a k−1 ,a k )+dist(a k ,a 1 )。dist(a1 ,a2 )+dist(a2 ,a3 )+⋯+dist(ak−1 ,ak )+dist(ak ,a1 )。 画个图感性理解一下，应该是很好懂的。 那么求一下 DFSDFSDFS序，每次操作相当于往集合里加入/删除一个元素。 假设插入 x，它DFSDFSDFS序左右两边分别是 yyy和zzz。那么答案加上 dist(x,y)+dist(x,z)−dist(y,z)dist(x,y)+dist(x,z)−dist(y,z)dist(x,y)+dist(x,z)−dist(y,z) 即可。 删除同理。还有，求 LCALCALCA就用个倍增或者树剖吧，TarjanTarjanTarjan 离线比较麻烦。 用 STLSTLSTL自带的 setsetset 容器维护起来很方便。你也可以手写树状数组/线段树/平衡树。