其实就是动态维护包含所有关键点的极小联通子树边权和。
暴力做法只要子树内有关键点就去遍历，所以按照 DFS 序顺序去遍历这些关键点肯定是没问题的。
用 set 维护即可。在 \(x\) 和 \(z\) 之间加入 \(y\)，答案加上 \(dis(x,y)+dis(y,z)-dis(x,y)\)，删除就反过来。
P3320 [SDOI2015] 寻宝游戏
发布时间 2023-11-01 09:17:26作者: 御坂夏铃
其实就是动态维护包含所有关键点的极小联通子树边权和。
暴力做法只要子树内有关键点就去遍历，所以按照 DFS 序顺序去遍历这些关键点肯定是没问题的。
用 set 维护即可。在 \(x\) 和 \(z\) 之间加入 \(y\)，答案加上 \(dis(x,y)+dis(y,z)-dis(x,y)\)，删除就反过来。