给一棵树，每次激活或熄灭一个点，每次问这些点都联通起来所需的最小总边权
若根据dfs序给所有点排序，为$v1,v2,v3....vk$，那么答案就是$(dis(v1,v2)+dis(v2,v3)+...+dis(vk-1,vk)+dis(vk,v1))/2$
只需要动态的维护这个序列，每次拿出前后两个点后用lca修改答案即可
毕竟现在开O2的题比比皆是，要是能少写个平衡树岂不美哉（我也不会写233
我们就默认使用的是c++11的标准吧
首先你要有一个结构体，并在里面重载一个bool类型的（）函数，先这样（这里以将数字按d数组的大小排序为例）：
struct cmp{bool operator () (const int &a,const int &b){return d[a]<d[b];}};
接下来这样声明set：
set<int,cmp>S;
我们这里声明迭代器时使用c++11特有的auto用法，看起来方便不少（set<int>::iterator)
这里以查找x的前驱后继为例（循环式的，即若x为最后一个数，后继就是第一个数，反过来同理
auto it=S.lower_bound(x),a=it,b=it; int l=(it==S.begin()?*--S.end():*--a); int r=(it==--S.end()?*S.begin():*++b);
注意这里end()函数返回的是个超尾，所以要--
这里我们看到迭代器的移动用加减即可，取值时用*即可
insert和erase，千万别记错了
S.insert(x);
S.erase(x);
接下来放上这道题的代码
1 #include<bits/stdc++.h> 2 #define N 100005 3 #define ll long long 4 using namespace std; 5 int n,q; 6 int h[N],to[2*N],nxt[2*N],w[2*N],etop; 7 void add(int a,int b,int c){to[++etop]=b,nxt[etop]=h[a],w[etop]=c,h[a]=etop;} 8 int fa[N][20],d[N],tot,dep[N]; 9 ll len[N][20]; 10 void dfs(int u){ 11 d[u]=++tot; 12 for(int i=1;i<=17;i++){ 13 fa[u][i]=fa[fa[u][i-1]][i-1]; 14 len[u][i]=len[u][i-1]+len[fa[u][i-1]][i-1]; 15 if(fa[u][i]==0)break; 16 } 17 for(int k=h[u],v=to[k];k;k=nxt[k],v=to[k]) 18 if(v!=fa[u][0]){ 19 fa[v][0]=u;len[v][0]=w[k]; 20 dep[v]=dep[u]+1; 21 dfs(v); 22 } 23 } 24 ll LCA(int x,int y){ 25 ll ans=0; 26 if(dep[x]<dep[y])swap(x,y); 27 for(int i=17;i>=0;i--) 28 if(fa[x][i]&&dep[fa[x][i]]>=dep[y]){ 29 ans+=len[x][i]; 30 x=fa[x][i]; 31 } 32 if(x==y)return ans; 33 for(int i=17;i>=0;i--) 34 if(fa[x][i]!=fa[y][i]){ 35 ans+=len[x][i]; 36 ans+=len[y][i]; 37 x=fa[x][i]; 38 y=fa[y][i]; 39 } 40 ans+=len[x][0]; 41 ans+=len[y][0]; 42 return ans; 43 } 44 struct cmp{bool operator () (const int &a,const int &b){return d[a]<d[b];}}; 45 set<int,cmp>S; 46 ll ans; 47 void ins(int x){ 48 S.insert(x); 49 auto it=S.lower_bound(x),a=it,b=it; 50 int l=(it==S.begin()?*--S.end():*--a); 51 int r=(it==--S.end()?*S.begin():*++b); 52 ans-=LCA(l,r); 53 ans+=LCA(l,x); 54 ans+=LCA(x,r); 55 } 56 void del(int x){ 57 auto it=S.lower_bound(x),a=it,b=it; 58 int l=(it==S.begin()?*--S.end():*--a); 59 int r=(it==--S.end()?*S.begin():*++b); 60 ans+=LCA(l,r); 61 ans-=LCA(l,x); 62 ans-=LCA(x,r); 63 S.erase(x); 64 } 65 char o[2]; 66 int main(){ 67 scanf("%d",&n); 68 for(int i=1,a,b,c;i<n;i++){ 69 scanf("%d%d%d",&a,&b,&c); 70 add(a,b,c),add(b,a,c); 71 } 72 dfs(1); 73 scanf("%d",&q); 74 while(q--){ 75 scanf("%s",o); 76 if(o[0]==‘?‘)cout<<ans/2<<endl; 77 else{ 78 int x;scanf("%d",&x); 79 if(o[0]==‘+‘)ins(x); 80 else del(x); 81 } 82 } 83 return 0; 84 }
原文：https://www.cnblogs.com/2017SSY/p/10948482.html
