General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
256921221 Practice:
fzxmd1
176E - 26 C++14 (GCC 6-32) Accepted 468 ms 23700 KB 2024-04-16 16:33:11 2024-04-20 18:43:28
→ Source
//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
int const N=1e5+10;
int n,q,fa[20][N],g[N],dep[N],dfn[N],rev[N];
vector< pair<int,int> >a[N];
inline void dfs(int x,int Fa){
    fa[0][x]=Fa,g[x]=g[Fa]+1,dfn[x]=++dfn[0],rev[dfn[0]]=x;
    for (auto i:a[x]){
        int v=i.first,w=i.second;
        if (v==Fa) continue;
        dep[v]=dep[x]+w,dfs(v,x);
    }
}
inline int LCA(int x,int y){
    if (g[x]<g[y]) swap(x,y);
    per(i,19,0) if (g[fa[i][x]]>=g[y]) x=fa[i][x];
    if (x==y) return x;
    per(i,19,0) if (fa[i][x]^fa[i][y]) x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
inline int dis(int x,int y){
    return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
int ans;set<int>s;
inline void add(int x){
    if (!s.size()) s.insert(dfn[x]);
    else{
        auto it1=s.upper_bound(dfn[x]);
        if (it1==s.end()) it1=s.begin();
        auto it2=s.upper_bound(dfn[x]);
        if (it2==s.begin()) it2=--s.end();
        else --it2;
        ans-=dis(rev[*it1],rev[*it2]);
        ans+=dis(x,rev[*it1]),ans+=dis(x,rev[*it2]);
        s.insert(dfn[x]);
    }
}
inline void del(int x){
    if (s.size()==1) s.erase(dfn[x]);
    else{
        auto it1=s.upper_bound(dfn[x]);
        if (it1==s.end()) it1=s.begin();
        auto it2=s.find(dfn[x]);
        if (it2==s.begin()) it2=--s.end();
        else --it2;
        ans+=dis(rev[*it1],rev[*it2]);
        ans-=dis(x,rev[*it1]),ans-=dis(x,rev[*it2]);
        s.erase(dfn[x]);
    }
}
inline void solve(){
    cin>>n;
    rep(i,1,n-1){
        int u,v,w;cin>>u>>v>>w;
        a[u].emplace_back(v,w);
        a[v].emplace_back(u,w);
    }
    dfs(1,0);
    rep(j,1,19) rep(i,1,n) fa[j][i]=fa[j-1][fa[j-1][i]];
    cin>>q;
    while (q--){
        char op;cin>>op;
        switch (op){
            case '+':{
                int x;cin>>x,add(x);
                break;
            }
            case '-':{
                int x;cin>>x,del(x);
                break;
            }
            case '?':{
                cout<<ans/2<<'\n';
                break;
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while (t--) solve();
    cerr<<"Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
    return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details