lca异象石

首先通过dfs求出每个节点的时间戳，即第一次访问该节点的时间，将时间戳按照从小到大的顺序进行排序，并用ans累计相邻两节点的路径长度，可以发现所求的答案为ans/2

运用set记录当前出现的异象石，当询问和删除时，就很容易找到它左边的和右边的异象石

设d[i]为从i到跟节点的距离，用差分的思想，从i到j的路径的长度dis(i,j)=di+dj-2*d lca(i,j)

• 当插入节点x时，找到x左边和右边的节点l，r（注意边界的情况）ans减去dis(l,r)再加上dis(l,x)+dis(x,r)

• 删除时思路也一样只是先加再减

• 对于询问输出ans/2

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct note{
    ll next,to,l;
}e[200005];
ll head[100005],dep[100005],d[100005],dfn[100005],h[100005],f[100005][25];
ll n,m,cnt,ans,num;
set<ll>s;
char ch;
void add(ll x,ll y,ll z){
    cnt++;
    e[cnt].next=head[x];
    e[cnt].to=y;
    e[cnt].l=z;
    head[x]=cnt;
}
void dfs(ll x,ll father,ll depth,ll l){
    d[x]=l;dep[x]=depth;
    f[x][0]=father;
    dfn[x]=++num;
    for(ll i=head[x];i;i=e[i].next){
        if(e[i].to==father)continue;
        dfs(e[i].to,x,depth+1,l+e[i].l);
    }
}
void st(){
    for(ll j=1;j<=20;j++)
        for(ll i=1;i<=n;i++)
            f[i][j]=f[f[i][j-1]][j-1];
}
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 x;
    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 path(ll x,ll y){
//    cout<<d[x]+d[y]-2*d[lca(x,y)]<<"\n";
    return d[x]+d[y]-2*d[lca(x,y)];
}
void solve(ll x,ll op){
//    cout<<x<<" "<<op<<"ff";
    set<ll>::iterator iter,l,r;
//    cout<<s.empty();
    if(op==-1)s.erase(dfn[x]);
    if(s.empty()){if(op==1)s.insert(dfn[x]);return;}
    iter=s.lower_bound(dfn[x]);
    if(iter==s.begin()||iter==s.end())l=s.begin(),r=s.end(),--r;
    else l=iter,r=iter,--l;
//    cout<<*l<<" "<<*r<<"\n";
    ans-=(path(h[*l],h[*r])*op);
    ans+=((path(x,h[*l])+path(x,h[*r]))*op);
    if(op==1)s.insert(dfn[x]);
}
int main(){
//    freopen("stone1.in","r",stdin);
//    freopen("stone.abc","w",stdout);
    scanf("%lld",&n);
    ll x,y,z;
    for(ll i=1;i<n;i++)scanf("%lld%lld%lld",&x,&y,&z),add(x,y,z),add(y,x,z);
    dfs(1,0,1,0);
    st();
    for(ll i=1;i<=n;i++)h[dfn[i]]=i;
//    for(ll i=1;i<=n;i++)cout<<d[i]<<" "<<dep[i]<<" "<<dfn[i]<<"\n";
    scanf("%lld",&m);
    while(m--){
        do{ch=getchar();}while(ch!='+'&&ch!='-'&&ch!='?');
        if(ch=='+')scanf("%lld",&x),solve(x,1);
        if(ch=='-')scanf("%lld",&x),solve(x,-1);
        if(ch=='?')printf("%lld\n",ans/2);
//        cout<<ans<<'\n';
    }
    return 0;
}