题解 P3320 【[SDOI2015]寻宝游戏】
Warriors_Cat
2020-12-02 19:03:53
是一道比较经典的题了吧，不过 NOIp 前做做老题也不错。
---
### $Solution:$
这题本质上就是求使动态点集连通的最小代价。
不放设这个点集为 $\{S_i\}$，$|\{S_i\}|=n$。
如果我们把 $S_i$ 按照其 $\mathrm{DFS}$ 序排序的话，那么这个最小代价便是：
$$2\sum_{i=1}^ndis(S_i, S_{i+1})$$
这里钦定 $S_{n+1}=S_1$。
证明其实很简单，考虑连通后的子树，每条边在 $\mathrm{DFS}$ 的时候会入一次，又出一次，所以每条边就贡献了两次。而按照 $\mathrm{DFS}$ 序相邻取距离就相当于一个 $\mathrm{DFS}$ 的过程。
于是，我们每次插入后删除的时候都能维护这个值就行了。很显然每次我们都要找它的前驱和后继。
动态插入/删除+找前驱后继？平衡树！
~~平衡树好长啊，不想打（~~
STL 中恰好有现成的平衡树 `set`，于是我们可以巧妙地运用 `set` 来解决此题。
两点间的距离可以直接用 $\mathrm{LCA}$ $O(\log n)$ 求。
于是整道题就做完了，时间复杂度为 $O((n+m)\log n)$。
写代码的时候，注意前驱后继的边界问题。
### $Code:$
由于笔者的特判有亿点多，所以此代码又臭又长，建议不做参考，但想看的同学还是可以看一下。
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
#define int long long
#define SI set <int> :: iterator
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 ^ 48); ch = getchar(); }
return x * f;
}
const int N = 100010;
struct edge{
int v, w, nxt;
}e[N << 1];
int head[N << 1], cnt, n, m, k, x, y, z, dep[N], dis[N], f[N][20], dfn[N], pos[N], ans;
char ch[10];
set <int> st;
SI it, it2, it3;
inline void add(int u, int v, int w){
e[++cnt].v = v;
e[cnt].w = w;
e[cnt].nxt = head[u];
head[u] = cnt;
}
inline void dfs(int u){
dfn[u] = ++k;
pos[k] = u;
for(register int i = head[u]; i; i = e[i].nxt){
int v = e[i].v, w = e[i].w;
if(dep[v]) continue;
dep[v] = dep[u] + 1;
dis[v] = dis[u] + w;
f[v][0] = u;
for(int j = 1; j <= 17; ++j) f[v][j] = f[f[v][j - 1]][j - 1];
dfs(v);
}
}
inline int lca(int a, int b){
if(dep[a] < dep[b]) a ^= b ^= a ^= b;
for(register int i = 17; i >= 0; --i) if(dep[f[a][i]] >= dep[b]) a = f[a][i];
if(a == b) return a;
for(register int i = 17; i >= 0; --i) if(f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
return f[a][0];
}
inline int pat(int a, int b){
return dis[a] + dis[b] - 2 * dis[lca(a, b)];
}
signed main(){
n = read(); m = read();
for(register int i = 1; i < n; ++i){
x = read(); y = read(); z = read();
add(x, y, z); add(y, x, z);
}
dfs(dep[1] = 1);
for(register int i = 1; i <= m; ++i){
x = read(); it = st.find(dfn[x]);
if(it == st.end()){
if(st.empty()){
st.insert(dfn[x]);
printf("%lld\n", ans);
continue;
}
it = st.lower_bound(dfn[x]);
if(it == st.end() || it == st.begin()){
it2 = st.end(); --it2;
ans -= pat(pos[*st.begin()], pos[*it2]);
ans += pat(pos[*st.begin()], x);
ans += pat(pos[*it2], x);
st.insert(dfn[x]);
}
else{
it2 = it; --it2;
ans -= pat(pos[*it2], pos[*it]);
ans += pat(pos[*it], x);
ans += pat(pos[*it2], x);
st.insert(dfn[x]);
}
}
else{
if(st.size() == 1){
ans = 0;
st.erase(st.begin());
printf("%lld\n", ans);
continue;
}
it = st.lower_bound(dfn[x]);
it3 = it; ++it3;
if(it3 == st.end()){
it2 = it; --it2;
ans += pat(pos[*st.begin()], pos[*it2]);
ans -= pat(pos[*st.begin()], x);
ans -= pat(pos[*it2], x);
st.erase(dfn[x]);
}
else if(it == st.begin()){
it2 = it; ++it2; it3 = st.end(); --it3;
ans += pat(pos[*it2], pos[*it3]);
ans -= pat(pos[*it2], x);
ans -= pat(pos[*it3], x);
st.erase(dfn[x]);
}
else{
it2 = it; --it2;
ans += pat(pos[*it2], pos[*it3]);
ans -= pat(pos[*it2], x);
ans -= pat(pos[*it3], x);
st.erase(dfn[x]);
}
}
printf("%lld\n", ans);
}
return 0;
}
```