[bzoj1912]异象石(set)

Description

Adera是Microsoft应用商店中的一款解谜游戏。

异象石是进入Adera中异时空的引导物，在Adera的异时空中有一张地图。这张地图上有N个点，有N-1条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的M个时刻中，每个时刻会发生以下三种类型的事件之一：

1.地图的某个点上出现了异象石（已经出现的不会再次出现）；

2.地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）；

3.向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。

请你作为玩家回答这些问题。

Input Format

第一行有一个整数N，表示点的个数。

接下来N-1行每行三个整数x,y,z，表示点x和y之间有一条长度为z的双向边。

第N+1行有一个正整数M。

接下来M行每行是一个事件，事件是以下三种格式之一：

• x 表示点x上出现了异象石
• x表示点x上的异象石被摧毁

?表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。

Output Format

对于每个 ?事件，输出一个整数表示答案。

Hint

对于100%的数据，1 ≤ n, m ≤ 10^5, 1 ≤ x, y ≤ n, x ≠ y, 1 ≤ z ≤ 10^9。

Solution

如果在\(A_1,A_2,A_3...A_k\)这些点上有异象石，则所需代价就是按照DFS序依次遍历这k个点再回到根的总距离。

即相邻2个石头的距离和加上\(A_1\)和\(A_k\)的距离除以2即为Ans,

那么动态维护增加与删除操作即可,

例如增加一个点x，那么设点x前一个DFS序的点为pre，后一个为nex,

那么\(Ans+=dis(x,pre)+dis(x,nex)-dis(pre,nex))\),

删除把 + = 换成 - = 即可。

关键在于如何维护点的前驱与后驱，可以用平衡树，但本蒟蒻不会，所以......（^_^），

那就用set维护就好，注意set是一个前闭后开的结构，所以end()返回的是最后一个元素的后驱

Code

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#define LL long long
#define N 100010
using namespace std;

set<int> s;
typedef set<int>::iterator It;
struct info {
    int to, nex, w;
} e[N * 2];
int n, m, _log, tot, head[N * 2];
int dep[N], f[N][20], p[N], dfn[N];
LL dis[N][20], Ans;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

inline void add_edge(int u, int v, int w) {
    e[++tot].to = v;
    e[tot].nex = head[u];
    head[u] = tot;
    e[tot].w = w;
}

void dfs(int u, int fa) {
    for (int i = 1; i <= _log; ++i) {
        f[u][i] = f[f[u][i - 1]][i - 1];
        dis[u][i] = dis[u][i - 1] + dis[f[u][i - 1]][i - 1];
    }

    for (int i = head[u]; i; i = e[i].nex) {
        int v = e[i].to;
        if (v == fa) continue;
        f[v][0] = u;
        dis[v][0] = e[i].w;
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

LL LCA(int u, int v) {
    LL res = 0;
    if (dep[u] > dep[v]) swap(u, v);
    int d = dep[v] - dep[u];

    for (int i = 0; i <= _log; ++i)
        if (d & (1 << i))
            res += dis[v][i], v = f[v][i];

    if (u == v) return res;

    for (int i = _log; i >= 0; i--)
        if (f[u][i] != f[v][i]) {
            res += dis[u][i] + dis[v][i];
            u = f[u][i];
            v = f[v][i];
        }

    return res + dis[u][0] + dis[v][0];
}

void dddfs(int u) {
    dfn[u] = ++tot;
    p[tot] = u;

    for (int i = head[u]; i; i = e[i].nex) {
        int v = e[i].to;
        if (!dfn[v])
            dddfs(v);
    }
}

inline It L(It it) {
    if (it == s.begin()) return --s.end();
    return --it;
}

inline It R(It it) {
    if (it == --s.end()) return s.begin();
    return ++it;
}

int main() {
    n = read();
    _log = log(n) / log(2);
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dfs(1, 0);
    tot = 0;
    dddfs(1);

    m = read();
    while (m--) {
        int ch = getchar();
        while (ch != '+' && ch != '-' && ch != '?') ch = getchar();
        It it;
        int t;
        if (ch == '?') printf("%lld\n", Ans / 2);
        else {
            int x = read();
            if (ch == '+') {
                if (s.size()) {
                    it = s.lower_bound(dfn[x]);
                    if (it == s.end()) it = s.begin();
                    t = *L(it);
                    Ans += LCA(x, p[t]) + LCA(x, p[*it]) - LCA(p[t], p[*it]);
                }
                s.insert(dfn[x]);
            } else {
                it = s.find(dfn[x]);
                t = *L(it), it = R(it);
                Ans -= LCA(x, p[t]) + LCA(x, p[*it]) - LCA(p[t], p[*it]);
                s.erase(dfn[x]);
            }
        }
    }
    return 0;
}