10132

题目描述

给出一棵\(N\)个点的树，有\(M\)个时刻，每个时刻有三种可能的事件：\(①\)某个点出现异象石；\(②\)某个点的异象石被摧毁；\(③\)求使异象石所在点被联通的边集的总长度。

思路

题目给出的使一棵树，我们考虑对于这个树确定一个根后，求出它的\(dfs\)序。那么事实上对于已知的异象石，我们对它按照\(dfs\)序排成一圈之后，所求的就是相邻两个节点的距离之和的\(\frac{1}{2}\)(然而这个结论我也不会证，只能画图感性理解)。所以我们只要为维护这个序列，并能够快速求两点间距离。求距离我们可以用倍增，而维护序列的前驱后继我们可以用平衡树维护，注意处理一下只有一个点的细节即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
const ll INF=1000000000;

ll nxt[N<<1],to[N<<1],tot,w[N<<1],head[N];
void add_edge(ll x,ll y,ll v)
{
    nxt[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    w[tot]=v;
}

ll dfn[N],dep[N],f[N][22],dis[N],idx,p[N];
void dfs(ll u,ll fa,ll s)
{
    dis[u]=s;dfn[u]=++idx;p[idx]=u;
    dep[u]=dep[fa]+1;
    for(ll i=0;i<20;i++)
        f[u][i+1]=f[f[u][i]][i];
    for(ll i=head[u];i;i=nxt[i])
    {
        ll v=to[i];
        if(v==fa)continue ;
        f[v][0]=u;
        dfs(v,u,s+w[i]);
    }
}
ll LCA(ll x,ll y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(ll i=20;i>=0;i--)
    {
        if(dep[f[x][i]]>=dep[y])x=f[x][i];
        if(x==y)return y;
    }
    for(ll i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    return f[x][0];
}
ll get_path(ll x,ll y)
{
//  cout<<x<<' '<<y<<endl;
    ll lca=LCA(x,y);
    return dis[x]+dis[y]-2*dis[lca];
}

struct Node
{
    ll lc,rc,w,v,cnt,siz;
}a[N];
ll root,sum,ss;
void upt(ll k)
{
    a[k].siz=a[a[k].lc].siz+a[a[k].rc].siz+a[k].cnt;
}
void zig(ll &k)
{
    ll t=a[k].lc;
    a[k].lc=a[t].rc;
    a[t].rc=k;
    a[t].siz=a[k].siz;
    upt(k);
    k=t;
}
void zag(ll &k)
{
    ll t=a[k].rc;
    a[k].rc=a[t].lc;
    a[t].lc=k;
    a[t].siz=a[k].siz;
    upt(k);
    k=t;
}
void insert(ll &k,ll key)
{
    if(!k)
    {
        k=++sum;
        a[k].siz=a[k].cnt=1;
        a[k].lc=a[k].rc=0;
        a[k].v=key;a[k].w=rand();
        return ;
    }
    else a[k].siz++;
    if(a[k].v==key)a[k].cnt++;
    else if(a[k].v<key)
    {
        insert(a[k].rc,key);
        if(a[a[k].rc].w<a[k].w)zag(k);
    }
    else
    {
        insert(a[k].lc,key);
        if(a[a[k].lc].w<a[k].w)zig(k);
    }
}
void f_delete(ll &k,ll key)
{
    if(a[k].v==key)
    {
        if(a[k].cnt>1)a[k].cnt--,a[k].siz--;
        else if(!a[k].lc||!a[k].rc)k=a[k].lc+a[k].rc;
        else if(a[a[k].lc].w<a[a[k].rc].w)zig(k),f_delete(k,key);
        else zag(k),f_delete(k,key);
        return ;
    }
    else a[k].siz--;
    if(a[k].v>key)
        f_delete(a[k].lc,key);
    else f_delete(a[k].rc,key);
}
ll findmin()
{
    ll x=root,res=INF;
    while(x)
    {
        res=min(res,a[x].v);
        x=a[x].lc;
    }
    return res;
}
ll findmax()
{
    ll x=root,res=-INF;
    while(x)
    {
        res=max(res,a[x].v);
        x=a[x].rc;
    }
    return res;
}
ll querypre(ll key)
{
    ll x=root,res=-INF;
    while(x)
    {
        if(a[x].v<key)res=max(res,a[x].v),x=a[x].rc;
        else x=a[x].lc;
    }
    if(res!=-INF)return res;
    else return findmax();
}
ll querynxt(ll key)
{
    ll x=root,res=INF;
    while(x)
    {
        if(a[x].v>key)res=min(res,a[x].v),x=a[x].lc;
        else x=a[x].rc;
    }
    if(res!=INF)return res;
    else return findmin();
}

ll read()
{
    ll res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res*w;
}
void write(ll x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void writeln(ll x)
{
    write(x);
    putchar('\n');
}

int main()
{
    ll n,m;
    n=read();
    for(ll i=1;i<n;i++)
    {
        ll x=read(),y=read(),z=read();
        add_edge(x,y,z);add_edge(y,x,z);
    }
    dfs(1,0,0);
    m=read();
    ll ans=0;
//  for(int i=1;i<=n;i++)
//      printf("%d ",dfn[i]);
//  printf("\n");
    while(m--)
    {
        char op;
        scanf(" %c",&op);
        if(op=='+')
        {
            ll x=read();ss++;
            if(ss<=1){insert(root,dfn[x]);ans=0;continue ;}
            ll l=querypre(dfn[x]),r=querynxt(dfn[x]);
//          cout<<l<<' '<<r<<endl;
            l=p[l];r=p[r];
            insert(root,dfn[x]);
            ans=ans+get_path(l,x)+get_path(x,r)-get_path(l,r);
        }
        else if(op=='-')
        {
            ll x=read();ss--;
            if(ss<=1){f_delete(root,dfn[x]);ans=0;continue ;}
            ll l=querypre(dfn[x]),r=querynxt(dfn[x]);
//          cout<<l<<' '<<r<<endl;
            l=p[l];r=p[r];
            f_delete(root,dfn[x]);
            ans=ans-get_path(l,x)-get_path(x,r)+get_path(l,r);
        }
        else
            writeln(ans/2);
//      cout<<ans<<endl;
    }
    return 0;
}