Adera是Microsoft应用商店中的一款解谜游戏。
异象石是进入Adera中异时空的引导物，在Adera的异时空中有一张地图。这张地图上有N个点，有N-1条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的M个时刻中，每个时刻会发生以下三种类型的事件之一：

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

链接🔗

[Contest Hunter Round #56] 异象石

题解

树上点的路径可以通过dfs序求出来,
(a[1] -> a[2] -> a[3] -> a[n] - > a[1])/2
然后插入和修改点，我们也可以进行动态维护，因为只有简单的前驱与后继的操作，可以直接用set来维护
PS: 统计距离要用long long

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int maxd = 1e5+10;
struct
{
    int v,net,w;
}e[maxd<<1];
int f[maxd],eid;
void insert(int a,int b,int c)
{
    e[eid].net= f[a];
    e[eid].v= b;
    e[eid].w = c;
    f[a] = eid++;
}
int p[maxd][30],d[maxd],id[maxd],num[maxd],tot;
int n,m,a,b,c,x;
long long ans =0,dist[maxd];
set<int> s;
set<int> :: iterator l,r;
void init()
{
    memset(f,-1,sizeof(f));
    memset(d,-1,sizeof(f));
    eid = 0; d[1] = 0;
}
void dfs(int x)
{
    id[x] = ++tot;
    num[tot] = x;
    for(int i = f[x]; i+1; i = e[i].net)
    {
        int v = e[i].v;
        if(d[v]==-1)
        {
            d[v] = d[x]+1;
            p[v][0] = x;
            dist[v] =(long long)(dist[x] + e[i].w);
            dfs(v);
        }    
    }
}
int lca(int a,int b)
{
    if(d[b] > d[a]) swap(a,b);
    for(int i = 25;i>=0;i--)
        if(d[p[a][i]]>=d[b]) a = p[a][i];
    if(a==b) return a;
    for(int i = 25;i>=0;i--)
        if(p[a][i]!=p[b][i]) a=p[a][i],b = p[b][i];
    return p[a][0];
}
long long dis(int x,int y)
{
    int ca = lca(x,y);
    return (long long)(dist[x] + dist[y] - 2*dist[ca]);
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    scanf("%d",&n);
    init();
    for(int i=1;i<n;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        insert(a,b,c);insert(b,a,c);
    }
    dfs(1);
    for(int j=1;j<=25;j++)
        for(int i=1;i<=n;i++)
            p[i][j] = p[p[i][j-1]][j-1];
    scanf("%d\n",&m);
    for(int i=1;i<=m;i++)
    {
        char str[2];
        scanf("%s",str);
        if(str[0] == '?') printf("%lld\n",ans/2);
        else if(str[0] == '+')
        {
            scanf("%d",&x);
            if(s.empty())
            {
                s.insert(id[x]);
                continue;
            }
            l = r = s.lower_bound(id[x]);
            if(r == s.begin()) l = s.end(); l--;
            if(r == s.end()) r = s.begin();
            ans +=(long long)(dis(num[*l],x) + dis(x,num[*r]) - dis(num[*l],num[*r]));
            s.insert(id[x]);
        }
        else
        {
            scanf("%d",&x);
            s.erase(id[x]);
            if(s.empty()) continue;
            l = r = s.lower_bound(id[x]);
            if(r == s.begin()) l = s.end(); l--;
            if(r == s.end()) r = s.begin();
            ans -= (long long)(dis(num[*l],x) + dis(x,num[*r]) - dis(num[*l],num[*r]));
        }
    }
    return 0;
}