异象石 题解

异象石 题解

在 Adera 的异时空中有一张地图。这张地图上有 N 个点，有 N−1 条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的 M个时刻中，每个时刻会发生以下三种类型的事件之一：

1. 地图的某个点上出现了异象石（已经出现的不会再次出现）；
2. 地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）；
3. 向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。

请你作为玩家回答这些问题。下图是一个例子，灰色节点表示出现了异象石，加粗的边表示被选为连通异象石的边集。

那么答案便是有异象石的每相邻两个石头加上首点与末点的距离除以 2

ans=dis(x_{1},x_{2})+dis(x_{2},x_{3})+……+dis(x_{n-1},x_{n})+dis(x_n,x_{1})

那么只需要动态维护具有异象石的点

当添加一个异象石在点 x 时,令点 x 的dfs序为 dfn(x)

设已有异象石的点集中， dfn(x) 的 前驱为 dfn(pre) ，后继为 dfn(nxt)

那么加入点 x 时，只需要使 ans+=dis(x,pre)+ dis(x,nxt)-dis(pre,nxt)

删除也一样

（怎么得到该性质？应该是每条边在算从前驱到 x 点（dis(x,pre)）和从 x 点到后继（dis(x,nxt)）的过程中都算了两次 ）

那么用 set 维护某个点的 dfs 序的前驱和后继就好了

Code:

#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+10;
struct edge{
    int next,to,v; 
}e[N*2];
int cnt,last[N],id[N],tim[N],n,m,tot,fa[N][21],d[N],sz;
ll ans=0,dis[N];

struct data{
    int id;
    bool operator < (const data m) const{
        return id<m.id;
    }
};
std::set<data> s;
void add(int a,int b,int c){
    cnt++;
    e[cnt].next=last[a],last[a]=cnt;
    e[cnt].to=b,e[cnt].v=c;
}
void dfs(int x,int f){
    d[x]=d[f]+1;fa[x][0]=f;id[x]=++tot;tim[tot]=x;
    for(int i=last[x];i;i=e[i].next){
        if(e[i].to==f) continue;
        dis[e[i].to]=dis[x]+e[i].v;
        dfs(e[i].to,x);
    }
}
void bz(){
    for(int i=1;i<=20;++i)
        for(int j=1;j<=n;++j)
            fa[j][i]=fa[fa[j][i-1]][i-1];
}
int lca(int x,int y){
    if(d[x]<d[y]) std::swap(x,y);
    for(int i=20;i+1;--i)
        if(d[fa[x][i]]>=d[y])
            x=fa[x][i];
    if(x==y) return x;
    for(int i=20;i+1;--i)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
ll countdis(int x,int y){
    x=tim[x],y=tim[y];
    int an=lca(x,y);
    return dis[x]+dis[y]-2*dis[an];
}
int main(){
//  freopen("data.in","r",stdin);
//  freopen("my.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n-1;++i){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    dfs(1,0); 
    bz();
    scanf("%d",&m);
    char op;int x;
    while(m--){
        scanf(" %c",&op);
        if(op=='+'){
            scanf("%d",&x);
            if(!sz){
                s.insert((data){id[x]});
                sz++;
            }
            else
                if(sz==1){
                    data tmp=*s.begin();
                    ans+=countdis(tmp.id,id[x]);
                    s.insert((data){id[x]});
                    sz++;
                }
                else{
                    data tmp=(data){id[x]};
                    std::set<data>::iterator it;
                    it=s.lower_bound(tmp);
                    if(it==s.end()){
                        it--;
                        ans+=countdis((*it).id,id[x]);
                        s.insert(tmp);
                    }
                    else
                        if(it==s.begin()){
                            ans+=countdis((*it).id,id[x]);
                            s.insert(tmp);
                        }
                        else{
                            data temp=*it;
                            it--;
                            ans-=countdis((*it).id,temp.id);
                            ans+=countdis(tmp.id,temp.id);
                            ans+=countdis(tmp.id,(*it).id);
                            s.insert(tmp);
                        }
                        sz++;
                    }
        }
        if(op=='?'){
            if(sz<=1){
                puts("0");
                continue;
            }
            ll out=ans;
            std::set<data>::iterator it=s.end();
            it--;
            out+=countdis((*s.begin()).id,(*it).id);
            out/=2;
            printf("%lld\n",out);
        }
        if(op=='-'){
            scanf("%d",&x);
            if(sz==1){
                ans=0;
                s.erase(s.begin());
                sz--;
            }
            else if(sz==2){
                ans=0;
                s.erase((data){id[x]});
                sz--;
            }
                else{
                    data tmp=(data){id[x]};
                    std::set<data>::iterator it;
                    it=s.lower_bound(tmp);
                    if(it==s.begin()){
                        data temp=*it;
                        it++;
                        ans-=countdis(temp.id,(*it).id);
                        s.erase(temp);
                    }
                    else{
                        std::set<data>::iterator temp=s.end();
                        temp--;
                        if(it==temp){
                            it--;
                            ans-=countdis((*temp).id,(*it).id);
                            s.erase(temp);
                        }
                        else{
                            temp=it;
                            temp--;
                            std::set<data>::iterator temp2=it;
                            temp2++;
                            ans-=countdis((*it).id,(*temp).id);
                            ans-=countdis((*it).id,(*temp2).id);
                            ans+=countdis((*temp2).id,(*temp).id);
                            s.erase(it);

                        }
                    }
                    sz--;
                }
        }

    }
    return 0;
}