---

目录

• [TOC]

题目链接

bzoj 3991: [SDOI2015]寻宝游戏

题解

发现每次答案就是把虚树上的路径*2

接在同一关键点上的点的dfs序是相邻的

那么用set动态维护dfs序列

每次删点加点就好了

代码

#include<set>

#include<cstdio>

#include<algorithm>

#define gc getchar()

#define pc putchar

#define LL long long

inline int read() {

    int x = 0,f = 1;

    char c = gc;

    while(c < '0' || c > '9') c = gc;

    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;

    return x * f;

}

void print(LL x) {

    if(x < 0) {

        pc('-');

        x = -x;

    }

    if(x >= 10) print(x / 10);

    pc(x % 10 + '0');

}

const int maxn = 100007;

int n,m;

struct node {

    int v,next,w;

} edge[maxn << 1];

int head[maxn],num = 0;

inline void add_edge(int u,int v,int w) {

    edge[++ num].v = v; edge[num].w = w; edge[num].next = head[u];head[u] = num;

}

std::set<int>s;

std::set<int> :: iterator it,qi,ho;

int deep[maxn],top[maxn],fa[maxn],son[maxn],siz[maxn];

LL dis[maxn];

void dfs1(int x,int f) {

    deep[x] = deep[f] + 1,fa[x] = f;

    siz[x] = 1;

    for(int i = head[x];i;i = edge[i].next) {

        int v = edge[i].v;

        if(v != f) {

            dis[v] = dis[x] + edge[i].w;

            dfs1(v,x);

            if(siz[v] > siz[son[x]]) son[x] = v;

            siz[x] += siz[v];

        }

    }

}

int cnt = 0,dfn[maxn],ra[maxn];

void dfs2(int x,int tp) {

    top[x] = tp; dfn[x] = ++ cnt;ra[cnt] = x;

    if(son[x]) dfs2(son[x],tp);

    for(int i = head[x];i;i = edge[i].next) {

        int v = edge[i].v;

        if(v == fa[x] || v == son[x]) continue;

        dfs2(v,v);

    }

}

int lca(int x,int y) {

    while(top[x] != top[y]) {

        if(deep[top[x]] > deep[top[y]]) x = fa[top[x]];

        else y = fa[top[y]];

    }

    return deep[x] > deep[y] ? y : x;

}

LL query(int x) {

    it = s.find(dfn[x]);

    if(it == s.begin()) {qi = s.end();qi --; }

    else {qi = it ;qi --; }

    ho = it;ho ++;

    if(ho == s.end()) ho = s.begin();

    return dis[ra[* ho]] + dis[ra[* it]] * 2 + dis[ra[* qi]] - dis[lca(ra[* ho],ra[* it])] * 2 - dis[lca(ra[* it],ra[* qi])] * 2;

}

bool vis[maxn];

LL work(int x) {

    it = s.find(dfn[x]);

    if(it == s.begin()) {qi = s.end();qi --; }

    else {qi = it; qi --;}

    ho = it;ho ++;

    if(ho == s.end()) ho = s.begin();

    return dis[ra[*ho]] + dis[ra[*qi]] - 2 * dis[lca(ra[*qi],ra[*ho])];

}

int main() {

    n = read(),m = read();

    for(int u,v,w,i = 1;i < n;++ i) {

        u = read(),v = read(),w = read();

        add_edge(u,v,w); add_edge(v,u,w);

    }

    LL ans = 0;

    dfs1(1,0);

    dfs2(1,1);

    for(int i = 1;i <= m;++ i) {

        int x = read();

        if(vis[x]) {

            ans -= query(x);

            ans += work(x);

            s.erase(dfn[x]),vis[x] = 0;

        } else {

            vis[x] = 1;

            s.insert(dfn[x]);

            ans -= work(x);

            ans += query(x);

        }

        printf("%lld\n",ans);

    }

    return 0;

}