「Solution」异象石

真·恶心题目, 调了两天。。。

异象石

link

分析

这道题即是求树上点集的最小覆盖边集合。

关键即是要考虑应该选择哪些边废话，这道题可以看作是「SDOI2015」寻宝游戏 的题面恶心版，问题的答案即是「SDOI2015」寻宝游戏 的答案的二分之一，因为你需要回到初始点，即每条在集合里的边都要走两遍。

转化后思路可以变得比较简单。

设当前新加入了一个点 x, 为了使x被覆盖掉，那么必定选从x出发到已经在已选中的路径上的距离x最近的点y(目标点)。

关键是求出该目标点。

画个草图(橙点是当前点x，红点是目标点，两个黑点分别是已插入的两个关键点pre, nxt)可以观察到：

新增的路径长为$add_1 + add_2 - del$即是$Dist(x, pre) + Dist (x,nxt) - Dist (pre, nxt)$。

问题即是求出pre和nxt.

根据dfs序可知，pre和nxt分别是dfn与dfn[x]相邻的两个点。

那么当当前点x处在最后或开头时就要再绕回开头或结尾(写得不清楚，自己理解。。。)。

就完了。

结论

即是先求出所有点的dfn，把dfn围成一圈，答案是每相邻两个点的距离的和的一半。

然后我忘了可以用set，就调了两天的平衡树。。。

主要是脑抽把dfn求错了没有发现。。。

代码

#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 5;
const int MAXM = 25;

int n, m, tot, t, st, fa[MAXN][MAXM], d[MAXN], dep[MAXN], dfn[MAXN], h[MAXN];
int root, tmp1, tmp2, tmp3, ans;

struct edge {
    int v, w;
    edge () {}
    edge (int V, int W) { v = V, w = W; }
};
vector<edge> G[MAXN];
void Addedge (int u, int v, int w) {
    G[u].push_back (edge (v, w));
    G[v].push_back (edge (u, w));
}

void dfs (int u, int fath, int s) {
	d[u] = s, dfn[u] = ++st, h[st] = u, dep[u] = dep[fath] + 1;
	for (int i = 1; i <= t; i++) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i].v, w = G[u][i].w;
		if (v == fath) continue;
		fa[v][0] = u;
		dfs (v, u, s + w);
	}
}

int Lca(int x, int y) {
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    for (int i = t; i >= 0; i--) {
        if (dep[fa[y][i]] >= dep[x]) {
            y = fa[y][i];
        }
    }
    if (x == y)
        return x;
    for (int i = t; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}

int Dist (int x, int y) {
	return d[x] + d[y] - 2 * d[Lca (x, y)];
}

struct Treap {
    int val, key, l, r, siz;
} s[MAXN];

void push_up (int p) {
    s[p].siz = s[s[p].l].siz + s[s[p].r].siz + 1;
}

void split (int p, int val, int& x, int& y) {
    if (p == 0) { x = y = 0; return; }
    if (s[p].val <= val) {
        x = p; split (s[p].r, val, s[p].r, y);
    } else {
        y = p; split (s[p].l, val, x, s[p].l);
    }
    push_up (p);
}

int merge (int x, int y) {
    if (!x || !y) return x + y;
    if (s[x].key < s[y].key) {
        s[x].r = merge (s[x].r, y);
        push_up (x);
        return x;
    } else {
        s[y].l = merge (x, s[y].l);
        push_up (y);
        return y;
    }
}

int newnode (int val) {
    s[++tot].val = val, s[tot].key = rand (), s[tot].siz = 1;
    return tot;
}

void insert (int val) {
    split (root, val, tmp1, tmp2);
    root = merge (merge (tmp1, newnode (val)), tmp2);
}

void remove (int val) {
    split (root, val, tmp1, tmp3);
    split (tmp1, val - 1, tmp1, tmp2);
    tmp2 = merge (s[tmp2].l, s[tmp2].r);
    root = merge (tmp1, merge (tmp2, tmp3));
}

int querykth (int p, int k) {
    while (1) {
        if (s[s[p].l].siz >= k) { p = s[p].l; continue; }
        if (s[s[p].l].siz + 1 == k) {
            return p;
        }
        k -= s[s[p].l].siz + 1, p = s[p].r;
    }
}

int querymin (int p) {
	int res = INF;
	while (p) {
		res = min (res, s[p].val);
		p = s[p].l;
	}
	return res;
}
int querymax (int p) {
	int res = -INF;
	while (p) {
		res = max (res, s[p].val);
		p = s[p].r;
	}
	return res;
}

int querypre (int val) {
	tmp1 = 0, tmp2 = 0;
    split (root, val - 1, tmp1, tmp2);
    if (tmp1 == 0) {
    	return querymax (root);
	}
    int res = s[querykth (tmp1, s[tmp1].siz)].val;
    root = merge (tmp1, tmp2);
	return res;
}
int querynxt (int val) {
	tmp1 = 0, tmp2 = 0;
    split (root, val, tmp1, tmp2);
    if (tmp2 == 0) {
    	return querymin (root);
	}
    int res = s[querykth (tmp2, 1)].val;
    root = merge (tmp1, tmp2);
	return res;
}

void insert_tree (int x) {
	if (s[root].siz + 1 <= 1) {
		insert (dfn[x]);
		ans = 0;
		return;
	}
	int pre = h[querypre (dfn[x])];
	int nxt = h[querynxt (dfn[x])];
	insert (dfn[x]);
	int add = Dist (pre, x) + Dist (nxt, x);
	int del = Dist (pre, nxt);
	ans = ans + add - del;
}

void remove_tree (int x) {
	if (s[root].siz - 1 <= 1) {
		remove (dfn[x]);
		ans = 0;
		return;
	}
	int pre = h[querypre (dfn[x])];
	int nxt = h[querynxt (dfn[x])];
	remove (dfn[x]);
	int del = Dist (pre, x) + Dist (nxt, x);
	int add = Dist (pre, nxt);
	ans = ans + add - del;
}

signed main () {
//	freopen ("data.in", "r", stdin);
//	freopen ("data.out", "w", stdout);
    scanf ("%lld", &n);
    t = 22;
    for (int i = 1, u, v, w; i < n; i++) {
        scanf ("%lld %lld %lld", &u, &v, &w);
        Addedge (u, v, w);
    }
    dfs (1, 0, 0);
    scanf ("%lld", &m);
    while (m--) {
        char opt; cin >> opt;
        int x;
        if (opt == '+') {
            scanf ("%lld", &x);
            insert_tree (x);
        } else if (opt == '-') {
            scanf ("%lld", &x);   
            remove_tree (x);
        } else {
            printf ("%lld\n", ans / 2);
        }
//        cout << "==" << ans / 2 << endl;
    }
    return 0;
}