LCA+DFS序

题目链接：CH#56C 异象石

题意：选择一条最短路将树上标记过的点连起来,并且点的个数是动态变化的。

如果我们按照$DFS$序将这些点排序，即$DFS$序小的在前面，构成一个环。我们可以发现这个环中相邻两个点得距离之和就是答案的二倍。我是这样理解的，既然按照$DFS$序将这些点排列起来(构成环)，按照$DFS$序将这几个点走完得到的路程是答案的两倍。因为每两个点之间的边必然递归一次，然后回溯一次，即每个边经过两次。

基于这样的思想，我们可以求解本题，但是如果暴力去做的话，单次操作的复杂度最高会变成$O(nlog_n)$ ,由于点是动态变化的，且每次只变一个点，我们可以用$set$来维护这些点，将它们的$DFS$序放入$set$中。设$dist$为两个点之间的距离(利用$LCA$很容易求得)，$ans$为答案的二倍，
每次插入一个点$x$时.找到这个点的前驱$pre$和后继$last$.(注意是环)

• $ans-=dist(pre,last)$，即将原来的断开。
• $ans+=dist(pre,x)+dist(last,pre)$,即加入新边。
• 将x节点的$DFS$序插入$set$

这样单词操作为$O(log_n)$，删除也是同理

    

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<string>
#include<set>
#include<cmath>
using namespace std;
const int N = 8e5 + 10;
const int up = 20;
#define lowbit(x) (x&(-x))
typedef long long ll;
struct Edge{
    int to, w, next;
}edge[N];
int head[N], tot, in[N], fat[N][22], dep[N],  top, vs[N];
int n, m;
set<int> s;
ll dis[N];
void addedge(int from, int to, int w)
{
    edge[++tot].to = to;
    edge[tot].w = w;
    edge[tot].next = head[from];
    head[from] = tot;
}
void dfs(int u)
{
    in[u] = ++top;
    vs[top] = u;
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to, w = edge[i].w;
        if (dep[v]) continue;
        dep[v] = dep[u] + 1;
        dis[v] = dis[u] + w;
        fat[v][0] = u;
        dfs(v);
    }
}
void dp()
{
    for (int j = 1; j <= up; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            fat[i][j] = fat[fat[i][j - 1]][j - 1];
        }
    }
}
int lca(int u, int v)
{
    if (dep[u] < dep[v]) swap(u, v);
    for (int j = up; j >= 0; j--)
    {
        if ((dep[u] - dep[v]) >> j & 1) u = fat[u][j];
    }
    if (u == v) return v;
    for (int j = up; j >= 0; j--)
    {
        if (fat[u][j] != fat[v][j]){
            u = fat[u][j];
            v = fat[v][j];
        }
    }
    return fat[u][0];
}

void init()
{
    top = tot = 0;
    for (int i = 0; i <= n; i++)
    {
        head[i] = -1;
        fat[i][0] = i;
        dep[i] = 0;
        dis[i] = 0;
    }
}
ll dist(int u, int v)
{
    return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}
int main()
{
    scanf("%d", &n);
    memset(head, -1, sizeof(head));
    //init();
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    dep[1] = 1;
    dfs(1);
    dp();
    scanf("%d", &m);
    ll ans = 0;
    while (m--)
    {
        char op[5];
        int x;
        scanf("%s", op);
        if (op[0] == '?')
        {
            printf("%lld\n", ans / 2);
        }
        else if (op[0] == '+')
        {
            scanf("%d", &x);
            if (s.empty())
            {
                s.insert(in[x]);
                continue;
            }
            else
            {
                auto it = s.lower_bound(in[x]);
                if (it == s.end()) it = s.begin();
                auto itt = it == s.begin() ? prev(s.end()) : prev(it);
                ans += dist(vs[*itt], x) + dist(x, vs[*it]) - dist(vs[*itt], vs[*it]);
                s.insert(in[x]);
            }
        }
        else
        {
            scanf("%d", &x);
            if (!s.count(in[x])) continue;
            auto it = s.lower_bound(in[x]);
            auto pre = it == s.begin() ? prev(s.end()) : prev(it);
            auto lst = next(it) == s.end() ? s.begin() : next(it);
            ans = ans - dist(vs[*pre], x) - dist(vs[*lst], x) + dist(vs[*pre], vs[*lst]);
            s.erase(it);
        }
    }
    return 0;
}