「BZOJ3991」[SDOI2015]寻宝游戏

Description

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

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

Input

第一行,两个整数 NNMM,其中 MM 为宝物的变动次数。
接下来的 N1N-1 行,每行三个整数 xxyyzz,表示村庄 xxyy 之间有一条长度为 zz 的道路。
接下来的 MM 行,每行一个整数 tt,表示一个宝物变动的操作。若该操作前村庄 tt 内没有宝物,则操作后村庄内有宝物;若该操作前村庄 tt 内有宝物,则操作后村庄内没有宝物。

Output

MM 行,每行一个整数,其中第 ii 行的整数表示第 ii 次操作之后玩家找到所有宝物需要行走的最短路程。若只有一个村庄内有宝物,或者所有村庄内都没有宝物,则输出 0

Sample Input

1
2
3
4
5
6
7
8
9
4 5
1 2 30
2 3 50
2 4 60
2
3
4
2
1

Sample Output

1
2
3
4
5
0
100
220
220
280

HINT

对于 10%10\% 的数据,1N100,1M1001 \leq N \leq 100, 1 \leq M \leq 100
对于 20%20\% 的数据,1N1000,1M10001 \leq N \leq 1000, 1 \leq M \leq 1000
对于另外 15%15\% 的数据,每个村庄最多成为两条道路的端点;
对于 100%100\% 的数据,1N100000, 1M100000, 1z1091 \leq N \leq 100000,\ 1 \leq M \leq 100000,\ 1 \leq z \leq 10^9

Solution

假设按照dfndfn序排序,宝物编号有{x1,x2,,xn}\{x_1,x_2,\cdots,x_n\}
那么答案就是dis(x1,x2)+dis(x2,x3)++dis(xn1,xn)dis(x_1,x_2)+dis(x_2,x_3)+\cdots+dis(x_{n-1},x_n)
最后加上dis(xn,x1)dis(x_n,x_1)就是答案。
考虑加入一个点,前驱为prepre,后驱为nxtnxt,那么答案增加
dis(pre,x)+dis(nxt,x)dis(pre,nxt)dis(pre,x)+dis(nxt,x)-dis(pre,nxt)
删除同理。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<set>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 210000;
int n, m;

struct Edge {
int u, v, nxt, w;
}e[N * 2];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].w = z;
}
int dfn[N], num;
ll dst[N];
int f[N][21], d[N];
int lca(int x, int y) {
if(d[x] > d[y]) swap(x, y);
for(int i = 20; ~i; --i)
if(d[f[y][i]] >= d[x]) y = f[y][i];
if(x == y) return x;
for(int i = 20;~i;--i)
if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
void dfs(int x, int F) {
dfn[x] = ++num;
f[x][0] = F;
d[x] = d[F] + 1;
for(int i = 1; i <= 20; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dst[y] = dst[x] + e[i].w;
dfs(y, x);
}
}
struct T {
bool operator()(int x, int y)const {
return dfn[x] < dfn[y];
}
}cmp;
set<int,T>v;
set<int,T>::iterator p, q;
bool a[N];
ll dis(int x, int y) {
return dst[x] + dst[y] - 2*dst[lca(x, y)];
}
int main() {
n = read(), m = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read(), z = read();
addedge(x, y, z);
addedge(y, x, z);
}
dfs(1, 1);
ll ans = 0;
for(int T = 1; T <= m; ++T) {
int x = read();
a[x] ^= 1;
if(a[x] == 0) {
p = v.lower_bound(x);
int t = 0;
if(p != v.begin()) {
q = p; --q;
ans -= dis(x, *q);
t = *q;
}
q = p; if((++q) != v.end()) {
ans -= dis(*q, x);
if(t) ans += dis(*q, t);
}
v.erase(p);
} else {
v.insert(x);
p = v.lower_bound(x);
int t = 0;
if(p != v.begin()) {
q = p; --q;
ans += dis(x, *q);
t = *q;
}
q = p; if((++q) != v.end()) {
ans += dis(*q, x);
if(t) ans -= dis(*q, t);
}
}
if(v.size() <= 1) puts("0");
else writeln(ans + dis(*v.begin(), *(--v.end())));
}
return 0;
}