异象石（就是sdio宝藏那题）

题解：

之前这道题写过两次题解了吧。。

实现的时候可以用set<int,cmp>来实现按照dfn排序

代码：

感觉别人的分类讨论比我的简单。。

但我觉得我这个写起来也不烦就不看别人的了。。

看了一下 发现他们是把一个的前驱后继处理为自己 于是就避免了分类讨论（我xxx）

linux复制出来行间距变成两倍了。。

#include <bits/stdc++.h>

using namespace std;

#define rll ll

#define IL inline

#define rep(i,h,t) for (rll i=h;i<=t;i++)

#define dep(i,t,h) for (rll i=t;i>=h;i--)

#define ll long long

const ll N=4e5;

struct re{

    ll a,b,c;

}e[N*];

ll cnt,head[N],l;

ll bz[][N];

ll sum[N];

void arr(ll x,ll y,ll z)

{

    e[++l].a=head[x];

    e[l].b=y;

    e[l].c=z;

    head[x]=l;

}

ll dfn[N],dep[N];

void dfs(ll x,ll y)

{

  dfn[x]=++cnt; dep[x]=dep[y]+; bz[][x]=y;

  for (rll u=head[x];u;u=e[u].a)

  {

      rll v=e[u].b;

    if (v!=y)

    {

      sum[v]=sum[x]+e[u].c;

      dfs(v,x);

    }

  }

}

ll lca(ll x,ll y)

{

    if (dep[x]<dep[y]) swap(x,y);

    dep(i,,) if (dep[bz[i][x]]>=dep[y]) x=bz[i][x];

    if (x==y) return x;

    dep(i,,) if (bz[i][x]!=bz[i][y]) x=bz[i][x],y=bz[i][y];

    return bz[][x];

}

struct cmp{

    bool operator () (ll x,ll y)

    {

        return dfn[x]<dfn[y];

    }

};

#define tp set<ll,cmp>::iterator

set<ll,cmp> S;

tp it,it2,it3;

IL tp pre(tp it)

{

    tp it2=it; it2--; return(it2);

}

IL tp nxt(tp it)

{

    tp it2=it; it2++; return(it2);

}

int main()

{

    freopen("1.in","r",stdin);

    freopen("1.out","w",stdout);

    ios::sync_with_stdio(false);

    ll n;

    cin>>n;

    rep(i,,n-)

    {

        ll x,y,z;

        cin>>x>>y>>z;

        arr(x,y,z); arr(y,x,z);

    }

    dfs(,);

    rep(i,,)

      rep(j,,n)

        bz[i][j]=bz[i-][bz[i-][j]];

    ll m;

    cin>>m;

    ll ans=;

    ll num=;

    rep(i,,m)

    {

        char cc; ll x;

        cin>>cc;

        if (cc=='+')

        {

            cin>>x; num++;

            ans+=*sum[x];

            it =S.insert(x).first;

            if (num==) continue;

            bool tt=;

            if (it==S.begin())

            {

                tt=;

                it2=nxt(it);

                it3=S.end(); it3--;

                if (num!=)

                                {

                  ans+=*sum[lca(*it2,*it3)];

                  ans-=*sum[lca(x,*it2)];

                  ans-=*sum[lca(x,*it3)];

                } else ans-=*sum[lca(x,*it2)];

            }

            it2=nxt(it);

            if (!tt&&it2==S.end())

            {

                tt=;

                it2=pre(it);

                it3=S.begin();

                if (num!=)

        {

                  ans+=*sum[lca(*it2,*it3)];

                  ans-=*sum[lca(x,*it2)];

                  ans-=*sum[lca(x,*it3)];

                } else ans-=*sum[lca(x,*it2)];

            }

            if (!tt)

            {

                it2=pre(it);

                it3=nxt(it);

                ans+=*sum[lca(*it2,*it3)];

                ans-=*sum[lca(x,*it2)];

                ans-=*sum[lca(x,*it3)];

            }

        }

        if (cc=='-')

        {

            cin>>x; num--;

            if (!num)

            {

                ans=; S.clear();

                continue;

            }

            it=S.find(x);

            ans-=*sum[x];

            bool tt=;

            if (it==S.begin())

            {

                tt=;

                it2=nxt(it);

                it3=S.end(); it3--;

                if (num>=)

                {

                  ans-=*sum[lca(*it2,*it3)];

                  ans+=*sum[lca(x,*it2)];

                  ans+=*sum[lca(x,*it3)];

                } else ans+=*sum[lca(x,*it3)];

            }

            it2=nxt(it);

            if (!tt&&it2==S.end())

            {

                tt=;

                it2=pre(it);

                it3=S.begin();

                if (num>=)

                {

                  ans-=*sum[lca(*it2,*it3)];

                  ans+=*sum[lca(x,*it2)];

                  ans+=*sum[lca(x,*it3)];

                } else ans+=*sum[lca(x,*it3)];

            }

            if (!tt)

            {

                it2=pre(it);

                it3=nxt(it);

                ans-=*sum[lca(*it2,*it3)];

                ans+=*sum[lca(x,*it2)];

                ans+=*sum[lca(x,*it3)];

            }

            S.erase(x);

        }

        if (cc=='?')

        {

            if (num<=) cout<<<<endl;

            else cout<<ans/<<endl;

        }

    }

    return ;

}