思路：
考虑按照 dfn 序将关键点的集合排序后为 \(a_0,a_1,\cdots,a_k\)，则答案为：
\[\frac{\sum\limits_{i=0}^k \operatorname{dis}(a_i,a_{(i+1) \bmod k})}{2}\]
简单证明一下：
需要找出包罗一些关键点的最小联通导出子图。
则随便以一个关键点为根，对于子树内没有关键点的子树直接丢掉，就形成了新树；新树的叶子节点绝对都是关键点。
我们要找出新树的边集数目，即在 dfs 搜索的时候，每条边会在搜入子树时颠末一次，出子树的时候颠末一次，总计每条边会颠末两次。
这个 dfs 搜索的过程等价于按照叶子节点 dfn 序的相邻取距离。
故我们需要动态维护上面谁人式子的答案，注意到每次我们只删除或插入一个数，直接使用 set 维护即可。
如果你想，也自己写均衡树。
时间复杂度为 \(O(Q \log N)\)。
P10930 异象石 与 CF176E Archaeology Code： [code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod) x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i=l;i--)using namespace std;typedef long double lb;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=1e5+10;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c |
