异象石

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2458 字
树上动态增删若干异象石，每次询问使当前所有异
一本通
例
正文

/*
原题：T1554 「一本通 4.4 例 3」异象石 (CH Round #56)
题意：树上动态增删若干异象石，每次询问使当前所有异象石连通所需的最小边权和（即最小生成子树总长）。
思路：把异象石按 DFS 序排序成环，总长 = 1/2 * Σdist(相邻两点)（含首尾）。用 std::set 按 dfn 维护，每次增删只更新前后两个邻居的贡献。
复杂度：O((N+M) log N)。
易错点：dist 为加权距离，必须用 long long；增删时前驱/后继要按环处理（首尾相接）；环上三点公式需除以 2。
*/
#include <bits/stdc++.h>
using namespace std;
const int LOG=20;
int n;
vector<vector<pair<int,int>>> g;
vector<int> dep;
vector<long long> dis;
vector<vector<int>> up;
vector<int> dfn;
int tim=0;
void dfs(int u,int p){
    dfn[u]=++tim;
    up[u][0]=p;
    for(int i=1;i<LOG;i++) up[u][i]=up[up[u][i-1]][i-1];
    for(auto&e:g[u]){
        int v=e.first,w=e.second;
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dis[v]=dis[u]+w;
        dfs(v,u);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=LOG-1;i>=0;i--)
        if(dep[x]-(1<<i)>=dep[y]) x=up[x][i];
    if(x==y) return x;
    for(int i=LOG-1;i>=0;i--)
        if(up[x][i]!=up[y][i]){ x=up[x][i]; y=up[y][i]; }
    return up[x][0];
}
long long dist(int x,int y){
    return dis[x]+dis[y]-2*dis[lca(x,y)];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    g.assign(n+1,vector<pair<int,int>>());
    for(int i=1;i<n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }
    dep.assign(n+1,0);
    dis.assign(n+1,0);
    dfn.assign(n+1,0);
    up.assign(n+1,vector<int>(LOG,0));
    dfs(1,0);
    int M;
    cin>>M;
    set<pair<int,int>> S;
    long long ans=0;
    while(M--){
        char op;
        cin>>op;
        if(op=='+'){
            int x;
            cin>>x;
            if(S.empty()){
                S.insert({dfn[x],x});
            }else{
                auto it=S.lower_bound({dfn[x],x});
                auto pred=(it==S.begin())?*S.rbegin():*prev(it);
                auto succ=(it==S.end())?*S.begin():*it;
                ans+=(dist(pred.second,x)+dist(x,succ.second)-dist(pred.second,succ.second))/2;
                S.insert({dfn[x],x});
            }
        }else if(op=='-'){
            int x;
            cin>>x;
            auto it=S.find({dfn[x],x});
            auto pred=(it==S.begin())?*S.rbegin():*prev(it);
            auto succ=(next(it)==S.end())?*S.begin():*next(it);
            ans-=(dist(pred.second,x)+dist(x,succ.second)-dist(pred.second,succ.second))/2;
            S.erase(it);
        }else{
            cout<<ans<<'\n';
        }
    }
    return 0;
}
异象石

正文

一本通·提高篇的其它内容
