【题意】给定n个点的带边权树，对于树上存在的若干特殊点，要求任选一个点开始将所有特殊点走遍后返回。现在初始没有特殊点，m次操作每次增加或减少一个特殊点，求每次操作后的总代价。n,m<=10^5。

【算法】虚树+DFS序+set

【题解】每次询问相当于求两倍虚树路径和。

模拟虚树上dfs序的转移会发现，dfs序相邻（1和n视为相邻）的两点路径值的总和，就是虚树路径和的两倍。

那么只需要用set维护特殊点集合，每次根据前驱后继更改答案。

#include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;const int maxn=100010;int n,m,first[maxn],tot,deep[maxn],in[maxn],dfsnum=0,f[maxn][30];ll dis[maxn];bool v[maxn];struct cmp{    bool operator ()(int x,int y){
    return in[x]
          
           
            s;set
            
             ::iterator it;struct edge{ int v,w,from;}e[maxn*2];void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}void dfs(int x,int fa){ in[x]=++dfsnum; for(int j=1;(1<
             
              <=deep[x];j++)f[x][j]=f[f[x][j-1]][j-1]; for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){ deep[e[i].v]=deep[x]+1; dis[e[i].v]=dis[x]+e[i].w; f[e[i].v][0]=x; dfs(e[i].v,x); }}int lca(int x,int y){ if(deep[x]
              
               =0;i--)if((1<
               
                <=deep[x]&&f[x][i]!=f[y][i]){ x=f[x][i];y=f[y][i]; } return f[x][0];}ll p(int x,int y){ return dis[x]+dis[y]-2*dis[lca(x,y)];}int main(){ scanf("%d%d",&n,&m); for(int i=1;i
                
                 1)sum+=p(a,b)-p(a,x)-p(b,x); s.erase(x);v[x]=0; } printf("%lld\n",sum); } return 0;}