bzoj3991 [SDOI2015]寻宝游戏 树链的并

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=3991

题解

貌似这个东西叫做树链的并，以前貌似写过一个类似的用来动态维护虚树。

大概就是最终的答案很显然是随便选一个被标记的点作为根以后所有被标记的点之间的路径的并的长度的二倍。

可以发现这个东西就等于把所有的点按照 dfs 序排序以后的序列，相邻的点的距离和再加上最后一个点到第一个点的距离。

可以使用 std::set 维护。

时间复杂度 \(O(n\log n)\)。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b , 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b , 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {
    int f = 0, c;
    while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
    x = c & 15;
    while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
    f ? x = -x : 0;
}

const int N = 1e5 + 7;

int n, m, dfc;
ll ans;
int v[N];
ll dis[N];
int dep[N], f[N], siz[N], son[N], top[N], dfn[N], pre[N];

struct Edge { int to, ne, w; } g[N << 1]; int head[N], tot;
inline void addedge(int x, int y, int z) { g[++tot].to = y, g[tot].w = z, g[tot].ne = head[x], head[x] = tot; }
inline void adde(int x, int y, int z) { addedge(x, y, z), addedge(y, x, z); }

inline void dfs1(int x, int fa = 0) {
    f[x] = fa, dep[x] = dep[fa] + 1, siz[x] = 1;
    for fec(i, x, y) if (y != fa) dis[y] = dis[x] + g[i].w, dfs1(y, x), siz[x] += siz[y], siz[y] > siz[son[x]] && (son[x] = y);
}
inline void dfs2(int x, int pa) {
    top[x] = pa, dfn[x] = ++dfc, pre[dfc] = x;
    if (!son[x]) return; dfs2(son[x], pa);
    for fec(i, x, y) if (y != f[x] && y != son[x]) dfs2(y, y);
}
inline int lca(int x, int y) {
    while (top[x] != top[y]) dep[top[x]] > dep[top[y]] ? x = f[top[x]] : y = f[top[y]];
    return dep[x] < dep[y] ? x : y;
}
inline ll dist(int x, int y) { return dis[x] + dis[y] - (dis[lca(x, y)] << 1); }

struct cmp {
    inline bool operator () (const int &x, const int &y) { return dfn[x] < dfn[y]; }
};
std::set<int, cmp> s;

inline void ins(int x) {
    std::set<int, cmp>::iterator p = s.lower_bound(x);
    int y = 0, z = 0;
    if (p != s.end()) y = *p, ans += dist(x, y);
    if (p != s.begin()) z = *--p, ans += dist(x, z);
    if (y && z) ans -= dist(y, z);
    s.insert(x);
}
inline void del(int x) {
    s.erase(x);
    std::set<int, cmp>::iterator p = s.lower_bound(x);
    int y = 0, z = 0;
    if (p != s.end()) y = *p, ans -= dist(x, y);
    if (p != s.begin()) z = *--p, ans -= dist(x, z);
    if (y && z) ans += dist(y, z);
}

inline void work() {
    dfs1(1), dfs2(1, 1);
    while (m--) {
        int x;
        read(x);
        if (!v[x]) v[x] = 1, ins(x);
        else v[x] = 0, del(x);
        if (s.empty()) puts("0");
        else {
            std::set<int, cmp>::iterator p = s.end();
            --p;
            // dbg("**** ans = %lld, *begin = %d, *end = %d, dist(4, 3) = %lld\n", ans, *s.begin(), *p, dist(4, 3));
            printf("%lld\n", ans + dist(*s.begin(), *p));
        }
    }
}

inline void init() {
    read(n), read(m);
    int x, y, z;
    for (int i = 1; i < n; ++i) read(x), read(y), read(z), adde(x, y, z);
}

int main() {
#ifdef hzhkk
    freopen("hkk.in", "r", stdin);
#endif
    init();
    work();
    fclose(stdin), fclose(stdout);
    return 0;
}

bzoj3991 [SDOI2015]寻宝游戏 树链的并

原文：https://www.cnblogs.com/hankeke/p/bzoj3991.html