CF176E Archaeology

CF176E Archaeology

学到了一个巨神的结论。。

虚树大小就是 dfs 序排序后相邻两个点的距离的和 + dfs序最左和最右两个点距离的和的一半

因为按照 dfs 序来走这些点,每个点向上的边都必然会在进入这个点的时候走一次,离开这个点的时候走一次。

所以导出子树这种东西一半都要往 dfs 序来想吧。。

然后这个东西的维护就变得简单了起来,开个 set 就做完了。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 998244353
typedef long long ll;
int n , m , z , q , blo;
int A[MAXN];
vector<pii> G[MAXN];
set<pii> S; long long ans;
int dfn[MAXN] , clo , bac[MAXN] , dep[MAXN] , g[MAXN][19];
ll sdep[MAXN];
void dfs( int u , int fa ) {
    dfn[u] = ++ clo; bac[clo] = u;
    for( auto t : G[u] ) if( t.fi != fa ) {
        int v = t.fi;
        dep[v] = dep[u] + 1 , sdep[v] = sdep[u] + t.se;
        g[v][0] = u;
        for( int k = 1 ; k < 19 ; ++ k ) if( g[g[v][k-1]][k-1] )
            g[v][k] = g[g[v][k-1]][k-1]; else break;
        dfs( t.fi , u );
    }
}
int lca( int u , int v ) {
    if( dep[u] < dep[v] ) swap( u , v );
    if( dep[u] != dep[v] )
        for( int k = 18 ; k >= 0 ; -- k ) if( dep[g[u][k]] >= dep[v] )
            u = g[u][k];
    if( u == v ) return u;
    for( int k = 18 ; k >= 0 ; -- k ) if( g[u][k] != g[v][k] )
        u = g[u][k] , v = g[v][k];
    return g[u][0];
}
ll dis( int u , int v ) {
    int l = lca( u , v );
    return sdep[u] + sdep[v] - 2 * sdep[l];
}
void solve() {
//    freopen("input","r",stdin);
//    freopen("ot","w",stdout);
    cin >> n;
    int u , v , w;
    rep( i , 1 , n - 1 ) scanf("%d%d%d",&u,&v,&w) , G[u].eb( mp( v , w ) ) , G[v].eb( mp( u , w ) );
    dep[1] = 1; dfs( 1 , 1 );
    char ch[4];
    cin >> q;
    rep( i , 1 , q ) {
        scanf("%s",ch);
        if( ch[0] == '-' ) {
            scanf("%d",&u);
            if( S.size() <= 1 ) { S.clear(); continue; }
            auto nxt = S.upper_bound( mp( dfn[u] , 0x3f3f3f3f ) ) , pre = nxt;
            -- pre;
            auto cur = pre;
            if( pre == S.begin() ) pre = S.end();
            -- pre;
            if( nxt == S.end() ) nxt = S.begin();
            int pr = pre -> se , nx = nxt -> se;
            ans -= dis( u , pr ) + dis( u , nx );
            ans += dis( pr , nx );
            S.erase( cur );
        } else if( ch[0] == '+' ) {
            scanf("%d",&u);
            if( !S.size() ) { S.insert( mp( dfn[u] , u ) ); continue; }
            auto nxt = S.upper_bound( mp( dfn[u] , 0x3f3f3f3f ) ) , pre = nxt;
            if( nxt == S.begin() ) pre = S.end();
            -- pre;
            if( nxt == S.end() ) nxt = S.begin();
            int pr = pre -> se , nx = nxt -> se;
            ans -= dis( pr , nx );
            ans += dis( pr , u ) + dis( u , nx );
            S.insert( mp( dfn[u] , u ) );
        } else {
            printf("%lld\n",ans / 2);
        }
    }
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}
\