前置知识
- 倍增/树剖 求LCA
- set/Splay/平衡树 维护一个时间戳序列
Description
给定一棵 \(n\) 个结点的树，边有边权，三种操作：
- 标记一个点
- 取消标记一个点
- 求使标记的所有点联通最少需要连的边的长度
Solution
一个很神奇的结论
记一个数组 \(dfn\) ，用来存dfs序的每个节点
设现有的被标记的点的dfs序从小到大排序后的集合为 \(\{ x_1, x_2, x_3 ... x_k \}\)
设两个点 \(u, v\) 的距离为 \(dis_{u, v}\)
那么答案为 \(dis_{x_1, x_2} + dis_{x_2 + x_3} + ... + dis_{x_{k - 1}, x_k} + dis_{x_k, x_1}\) 的一半
那么我们用一个数据结构维护标记的点的序列即可，维护的时候顺便统计答案，询问时直接输出
我选择Splay，因为我不会set
对答案的统计：
当标记一个点时，设这个点的dfs序为 \(x\)，序列中上一个点为 \(l\)，下一个点为 \(r\)，那么新增点的贡献为
\[\large dis_{pre_l, pre_x} + dis_{pre_x, pre_r} - dis_{pre_l, pre_r}
\]
取消标记一个点的处理方式类似（刚好反着）
注意序列里维护的是结点的dfs序，而求dis是用的是结点的编号
如果序列中没有 \(l\) 和 \(r\) 时注意特判一下
Code
/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 4e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
struct edge{
int to, w, nxt;
}e[MAXN << 1];
int head[MAXN], num_edge;
int n, m, Ans = 0, Cnt = 0;
int dis[MAXN], cnt = 0;
int dep[MAXN], siz[MAXN], son[MAXN], fath[MAXN], top[MAXN], dfn[MAXN], pre[MAXN];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
void add_edge(int from, int to, int w) { e[++num_edge] = (edge){to, w, head[from]}, head[from] = num_edge; }
namespace Cut{
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1, siz[u] = 1, fath[u] = fa;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa) continue;
dis[v] = dis[u] + e[i].w;
dfs(v, u);
siz[u] += siz[v];
if(siz[son[u]] < siz[v]) son[u] = v;
}
}
void dfs2(int u, int tp) {
dfn[u] = ++cnt, pre[cnt] = u, top[u] = tp;
if(son[u]) dfs2(son[u], tp);
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fath[u] || v == son[u]) continue;
dfs2(v, v);
}
}
int Get_Lca(int u, int v) {
while(top[u] != top[v]) dep[top[u]] < dep[top[v]] ? v = fath[top[v]] : u = fath[top[u]];
return dep[u] < dep[v] ? u : v;
}
}
namespace Splay{
#define lson son[now_][0]
#define rson son[now_][1]
#define f fa[now_]
int root, fa[MAXN], son[MAXN][2], node_num = 1;
int val[MAXN], cnt[MAXN], siz[MAXN];
int top = 0, bin[MAXN];
void Push_up(int now_){
siz[now_] = cnt[now_];
if(lson) siz[now_] += siz[lson];
if(rson) siz[now_] += siz[rson];
}
void Clear(int now_){
lson = rson = f = val[now_] = cnt[now_] = siz[now_] = 0;
bin[++top] = now_;
}
int NewNode(int fa_, int val_){
int now_ = (top ? bin[top--] : ++node_num);
fa[now_] = fa_;
val[now_] = val_;
siz[now_] = cnt[now_] = 1;
return now_;
}
int Whichson(int now_) { return now_ == son[f][1]; }
void Rotate(int now_){
int fa_ = f, w = Whichson(now_);
if(fa[f]) son[fa[f]][Whichson(fa_)] = now_;
fa[now_] = fa[f];
son[fa_][w] = son[now_][w ^ 1];
fa[son[fa_][w]] = fa_;
son[now_][w ^ 1] = fa_;
fa[fa_] = now_;
Push_up(fa_), Push_up(now_);
}
void Splay(int now_){
for( ; f; Rotate(now_)){
if(fa[f]) Rotate(Whichson(now_) == Whichson(f) ? f : now_);
}
root = now_;
}
void Insert(int now_, int fa_, int val_){
if(now_ && val[now_] != val_){
Insert(son[now_][val[now_] < val_], now_, val_);
return ;
}
if(val[now_] == val_) ++ cnt[now_];
if(!now_){
now_ = NewNode(fa_, val_);
if(f) son[f][val[f] < val_] = now_;
}
Push_up(now_), Push_up(f), Splay(now_);
}
int Find(int now_, int val_){
if(!now_) return false;
if(val_ < val[now_]) return Find(son[now_][0], val_);
if(val_ == val[now_]){
Splay(now_);
return true;
}
return Find(rson, val_);
}
void Delete(int val_){
if(!Find(root, val_)) return ;
if(cnt[root] > 1) {
-- cnt[root];
Push_up(root);
return ;
}
int oldroot = root;
if(!son[root][0] && !son[root][1]){
root = 0;
} else if(!son[root][0]){
root = son[root][1], fa[root] = 0;
} else if(!son[root][1]){
root = son[root][0], fa[root] = 0;
} else if(son[root][0] && son[root][1]){
int leftmax = son[root][0];
while(son[leftmax][1]) leftmax = son[leftmax][1];
Splay(leftmax);
son[root][1] = son[oldroot][1], fa[son[root][1]] = root;
}
Clear(oldroot), Push_up(root);
}
int QueryRank(int val_){
Insert(root, 0, val_);
int ret = siz[son[root][0]] + 1;
Delete(val_);
return ret;
}
int QueryVal(int rk_){
int now_ = root;
while(true){
if(!now_) return -1;
if(lson && siz[lson] >= rk_){
now_ = lson;
} else{
rk_ -= lson ? siz[lson] : 0;
if(rk_ <= cnt[now_]){
return val[now_];
}
rk_ -= cnt[now_];
now_ = rson;
}
}
}
int QueryPre(int val_){
Insert(root, 0, val_);
int now_ = son[root][0];
while(rson) now_ = rson;
Delete(val_);
return val[now_];
}
int QueryNext(int val_){
Insert(root, 0, val_);
int now_ = son[root][1];
while(lson) now_ = lson;
Delete(val_);
return val[now_];
}
}
using namespace Splay;
using namespace Cut;
int Get_dis(int u, int v) { return dis[u] + dis[v] - 2 * dis[Get_Lca(u, v)]; }
signed main()
{
n = read();
for(int i = 1, u, v, w; i < n; ++i) {
u = read(), v = read(), w = read();
add_edge(u, v, w), add_edge(v, u, w);
}
dfs(1, 0), dfs2(1, 1);
m = read();
char ch;
for(int i = 1, x, l, r; i <= m; ++i) {
cin >> ch;
if(ch == '+') {
x = read();
l = pre[QueryPre(dfn[x])];
r = pre[QueryNext(dfn[x])];
if(l) Ans += Get_dis(l, x);
if(r) Ans += Get_dis(x, r);
if(l && r) Ans -= Get_dis(l, r);
// Ans += 2 * dis[Get_Lca(l, r)] + dis[x] - 2 * dis[Get_Lca(l, x)] + dis[x] - 2 * dis[Get_Lca(x, r)];
Insert(root, 0, dfn[x]);
} else if(ch == '-') {
x = read();
l = pre[QueryPre(dfn[x])];
r = pre[QueryNext(dfn[x])];
if(l) Ans -= Get_dis(l, x);
if(r) Ans -= Get_dis(x, r);
if(l && r) Ans += Get_dis(l, r);
// Ans -= (2 * dis[Get_Lca(l, r)] + dis[x] - 2 * dis[Get_Lca(l, x)] + dis[x] - 2 * dis[Get_Lca(x, r)]);
Delete(dfn[x]);
} else {
// if(Cnt == 1) printf("0\n");
// else printf("%lld\n", Ans / 2);
l = pre[QueryVal(1)], r = pre[QueryVal(Cnt)]; // 我选择最后处理序列两端点
int Res = Ans; //记个变量暂时存储答案
if(l && r) Res += Get_dis(l, r);
printf("%lld\n", Res / 2);
}
}
return 0;
}
鸣谢
- 《信息学奥赛一本通》