Luogu3320 - [SDOI2015]寻宝游戏

2017/10/24

题目

小B最近正在玩一个寻宝游戏,这个游戏的地图中有 N 个村庄和 N-1 条道路,并且任何两个村庄之间 有且仅有一条路径可达。游戏开始时,玩家可以任意选择一个村庄,瞬间转移到这个村庄,然后可以任 意在地图的道路上行走,若走到某个村庄中有宝物,则视为找到该村庄内的宝物,直到找到所有宝物并 返回到最初转移到的村庄为止。

小 B 希望评测一下这个游戏的难度,因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这 个游戏中宝物经常变化,有时某个村庄中会突然出现宝物,有时某个村庄内的宝物会突然消失,因此小 B 需要不断地更新数据,但是小 B 太懒了,不愿意自己计算,因此他向你求助。为了简化问题,我们 认为最开始时所有村庄内均没有宝物。

树的大小 N, 操作数 M <= 1e5 边权 <= 1e9

解法

观察样例,会发现答案总是和所有宝物出现点及他们的 LCA 有关。

考虑虚树做法,维护 DFS 序,这个回路的长度等价于所有宝物点按 DFS 序排序后,相邻两点间的距离和 加上起点到终点的距离。

可以通过 std::set<pair<int, int> > 大力维护二元组 (DFN[x], [x])

记得开 LL 。

事实上这是一道模板题。有关虚树的一些练习题

代码

为什么这么长…

我好菜啊。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <cassert>
using namespace std;
const int SIZ = 2e5 + 2007;
typedef pair<int, int> pii;
typedef long long LL;

int N, M;

struct tgno {
    int v, w;
    tgno *n;
} POOL[SIZ], *Head[SIZ]; int ppos;

void _add(int u, int v, int w) {
    POOL[ppos].v = v;
    POOL[ppos].w = w;
    POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

void addEdge(int u, int v, int w) {
    _add(u, v, w), _add(v, u, w);
}

int id[SIZ]; int T;
int fa[SIZ][27];
LL dis[SIZ];
int dep[SIZ];
void dfs(int u, int pre = 0, int dd = 1) {
    dep[u] = dd;
    id[u] = ++T;
    fa[u][0] = pre;
    for(int i=1;i<27;i++) fa[u][i] = fa[fa[u][i-1]][i-1];

    typedef tgno* It;
    for(It i=Head[u];i;i=i->n) {
        if(i->v != pre) {
            dis[i->v] = dis[u] + i->w;
            dfs(i->v, u, dd + 1);
        }
    }
}

int lca(int a, int b) {
    if(dep[a] > dep[b]) swap(a, b);

    for(int i=26;i>=0;i--) {
        if(dep[fa[b][i]] >= dep[a]) b = fa[b][i];
    }

//  printf("%d %d %d %d\n", a, b, dep[a], dep[b]);
    assert(dep[a] == dep[b]);

    if(a == b) return a;

    for(int i=26;i>=0;i--) {
        if(fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
    }

    assert(a != b && fa[a][0] == fa[b][0]);

    return fa[a][0];
}

LL dist(int a, int b) {
    int l = lca(a, b);
    return dis[a] + dis[b] - (dis[l]<<1);
}

int flag[SIZ];
int main() {
    scanf("%d %d", &N, &M);

    int u, v, w;
    for(int i=1;i<N;i++) {
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u, v, w);
    }

    dfs(1);

    set<pii> s; int t;
    LL ans = 0;
    for(int j=1;j<=M;j++) {
        scanf("%d", &t);
        typedef set<pii>::iterator It;

        if(flag[t]) {
            It i = s.find(pii(id[t], t));
            assert(i != s.end());
            It nxt = ++i; --i;
            It pre;

            if(i != s.begin()) {
                pre = --i; ++i;
                ans -= dist((*pre).second, (*i).second);
            }

            if(nxt != s.end()) {
                ans -= dist((*i).second, (*nxt).second);
            }

            if(i != s.begin() && nxt != s.end()) {
                ans += dist((*pre).second, (*nxt).second);
            }

            s.erase(pii(id[t], t));
            flag[t] = 0;
        } else {
            s.insert(pii(id[t], t));
            flag[t] = 1;

            It i = s.find(pii(id[t], t));
            assert(i != s.end());
            
            It nxt = ++i; --i;
            It pre;

            if(i != s.begin()) {
                pre = --i; ++i;
                ans += dist((*pre).second, (*i).second);
            }

            if(nxt != s.end()) {
                ans += dist((*i).second, (*nxt).second);
            }

            if(i != s.begin() && nxt != s.end()) {
                ans -= dist((*pre).second, (*nxt).second);
            }
        }

        if(s.size()) {
            It lst = s.end(); --lst;
//          printf("%d %d\n", (*s.begin()).second, (*lst).second);
            printf("%lld\n", ans + dist((*s.begin()).second, (*lst).second));
        } else puts("0");
    }
}