某岛

… : "…アッカリ~ン . .. . " .. .
March 14, 2020

UOJ 87. mx 的仙人掌

参考资料
官方题解
https://blog.bill.moe/uoj87-mxcactus/

题意简述

给定一个仙人掌,每次从中选取几个关键节点,求它们之间两两之间距离的最大值。

解题报告

对于树的情况,如果你只会虚树或者树分治,对于仙人掌你肯定也只能这么做了。
—— 官方题解

所以这个题乃会几种做法,取决于树的版本的那个问题,你会几种做法。官方题解 的六、七、八、九,提供了四种思路。这里先实现第一个算法 —— 虚仙人掌。

虚仙人掌

虚树

先当成树做,拿个 30 分再说。。。这里我用 f[] 数组记录向下的最长距离,然后在更新 f[u] 之前,先用 f[v] 和 f[u] 一起更新一下全局的直径,这样就不需要记录次大值了!

提交记录

const int N = int(3e5) + 9, LV = 21;

VII adj[N]; int dfn[N], lfn[N], dep[N]; LL depp[N];
int tt;

int n,m,cnt,ind,top;
int fa[N][LV];

bool cmp(int a,int b) {
    return dfn[a]<dfn[b];
}
void dfs(int u) {
    dfn[u] = ++tt;
    for (auto it: adj[u]) {
        int v = it.fi, w = it.se; if (v == fa[u][0]) continue;
        fa[v][0] = u; for (int lv=0;fa[v][lv+1]=fa[fa[v][lv]][lv];++lv);
        dep[v] = dep[u] + 1;
        depp[v] = depp[u] + w;
        dfs(v);
    }
    lfn[u] = tt;
}
inline int move_up(int x, int t){
    for (int lv=0;t;++lv,t>>=1)
        if (t&1) x = fa[x][lv];
    return x;
}
inline int move_to(int x, int t){
    return move_up(x, dep[x]-t);
}
inline int lca(int x, int y) {
    if (dep[x]>dep[y]) swap(x,y); y=move_to(y, dep[x]); if (x==y) return x;
    DWN(lv, LV, 0) if (fa[x][lv]!=fa[y][lv]) x = fa[x][lv], y = fa[y][lv];
    return fa[x][0];
}
inline int dist(int x, int y) {
    return dep[x] + dep[y] - 2*dep[lca(x,y)];
}

namespace Virtual_Tree {
    VI adj[N]; int sta[N], top;
    LL f[N], diameter;

    void dfs(int u) {
        f[u] = 0; for (auto v: adj[u]) {
            dfs(v); LL w = depp[v] - depp[u]; f[v] += w;
            checkMax(diameter, f[u] + f[v]);
            checkMax(f[u], f[v]);
        }
        checkMax(diameter, f[u]);
    }

    void gao() {
        VI T; Rush {
            int x; RD(x);
            T.PB(x);
        }
        UNQ(T, cmp); DWN(i, SZ(T)-1, 0) {
            int z = lca(T[i], T[i+1]);
            T.PB(z);
        }
        UNQ(T, cmp); top = 0; for (auto u: T) {
            while (top && lfn[sta[top]] < dfn[u]) --top;
            if (top) adj[sta[top]].PB(u); sta[++top] = u;
        }

        diameter = -INFF; dfs(T[0]);
        printf("%lld\n", diameter);
        for (auto u: T) adj[u].clear();
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n, m); DO(m) {
        int x, y, w; RD(x, y, w);
        adj[x].PB({y, w});
        adj[y].PB({x, w});
    }
    dfs(1); Rush Virtual_Tree::gao();
}

虚仙人掌

首先对这类题目来说,通常的做法,是 dfs 的时候,找到环,然后再环上手工 dp 一次(但其实我总是敲错,需要依靠底力),把经过环的结果统计到答案,并更新到环上的根节点。
事实上对于 BZOJ 1023. [SHOI2008]cactus仙人掌图IOI 2008 D2T1 Islands 我们就是这样做的(分别是 直径 和 最长链,转移方程几乎一样)。

但我们发现并不是总能靠底力凹出来,比如 BZOJ 2125: 最短路,树上两点的最短路需要求 lca,仙人掌上怎么求 lca,似乎需要大量 if-else 判断 = =!!!
这个题的情况类似,因为在构建虚树的过程中,我们也需要求 lca。

这个时候我们就需要使用一种 常用的技巧 圆方树。参见 圆方树——处理仙人掌的利器

简单说来,圆方树就是把环边都去掉,新建一个 方点 来代替这个环,用环上的根节点连一条边到她,在从她到每个环上的其他节点连一条边,形成菊花形状以拆环为树(怎么样?是不是很像 block-cut tree)。

具体实作的话,先建三个结构体,分表表示 —— 原图,圆方树,虚树。分别记作 G,C,T。求圆方树的过程,可以类比 tarjan 求双联通分量,我这边是在最深的节点拉回反向边的时候,把环抠出来的(因而需要取个反)。
这里连向方点的权值为 0,而从方点连出的边的权值为左右两条路径的长度取 min。

紧接着在 C 上再 dfs 一次,预处理出 dp 和 lca 所需要的信息,为构造虚树做准备。最后求虚树的地方,和 之前写的代码 唯一的不同,是如果是从方点连出去的边,需要把这个环上连出去的那个孩子也加到树中,因为我们需要这些节点来正确处理环上的 DP。

    void add_edge(int x, int y) {
        if (x > G.n && x != C.fa[0][y]) { // 如果是从方点连出去,并且 y 不是连出去的那个孩子。
            int z = C.move_up(y, C.dep[y]-C.dep[x]-1);
            adj[x].PB(z);
            x = z;
        }
        adj[x].PB(y);
    }

这个地方也是之前裸凹的时候最麻烦的地方,因为现在有了圆方树,所以几行就处理了掉了w。

接下来是下一个容易错的地方,以样例来说,在建立虚树的时候我们会把 2 和 9 所在的这个环也加到虚树里,而这个环本身的信息有可能会节外生枝,包含一些本不应该被考虑到节点(这里是 7),所以我们更新答案的时候干脆只用圆点的信息更新即可(上面 add_edge 里补上的节点并不会影响)。

参见 下图

最后说一个让我 wa 成傻逼的地方,就是最后的资源回收。。。因为这种虚树的题通常我们是不能无脑 memset 的,但是我们刚才构建虚树的时候,中间又加入了一些新的节点,所以直接 for 循环那个数组的话会错。。
所以,最好在遍历树结束的同时把这些不用的信息都清理掉。。。

提交记录


const int N = int(6e5) + 9, LV = 21;
int sta[N], top;

struct Raw_Graph {
    map<int, int> adj[N]; int dfn[N], low[N], tt; LL D[N];
    int n;

    void add_edge(int x, int y, int w) {
        if (!CTN(adj[x], y)) {
            adj[x][y] = w;
            adj[y][x] = w;
        } else {
            checkMin(adj[x][y], w);
            checkMin(adj[y][x], w);
        }
    }

    void init() {
        RD(n); Rush {
            int x, y, w; RD(x, y, w);
            add_edge(x, y, w);
        }
    }
    void tarjan(int = 1, int = -1);
} G;

struct Cactus_Tree {
    vector<pair<int, LL> > adj[N]; int dfn[N], lfn[N], tt, dep[N]; LL D[N], L[N];
    int fa[LV][N];
    int n;

    void add_edge(int x, int y, LL w) {
        adj[x].PB({y, w});
    }

    inline int move_up(int x, int t){
        for (int lv=0;t;++lv,t>>=1)
            if (t&1) x = fa[lv][x];
        return x;
    }
    inline int lca(int x, int y) {
        if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;
        DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
        return fa[0][x];
    }

    void dfs(int u = 1) {
        dfn[u] = ++tt;
        ECH(it, adj[u]) {
            int v = it->fi; LL w = it->se;
            dep[v] = dep[u] + 1; D[v] = D[u] + w;
            fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
            dfs(v);
        }
        lfn[u] = tt;
    }

    void init() {
        n = G.n; G.tt = 0; G.tarjan();
        tt = 0; dfs();
    }
} C;

void Raw_Graph::tarjan(int u, int p) {
    low[u] = dfn[u] = ++tt;
    sta[++top] = u;
    ECH(it, adj[u]) {
        int v = it->fi, w = it->se; if (v == p) continue;
        if (!dfn[v]) {
            D[v] = D[u] + w; tarjan(v, u);
            checkMin(low[u], low[v]);
            if (dfn[v] == low[v]) C.add_edge(u, v, w); // tree edge
        } else if (dfn[v] < dfn[u]) { // find circle
            checkMin(low[u], dfn[v]);
            C.add_edge(v, ++C.n, 0); C.L[C.n] = D[u]-D[v]+w;
            for (int i=top;sta[i]!=v;--i) {
                LL d = D[sta[i]] - D[v];
                C.add_edge(C.n, sta[i], min(d, C.L[C.n]-d));
            }
            RVS(C.adj[C.n]);
        }
    }
    --top;
}

bool cmp(int a, int b) {
    return C.dfn[a] < C.dfn[b];
}

struct Virtual_Tree {

    VI adj[N];
    LL f[N], z;

    void add_edge(int x, int y) {
        if (x > G.n && x != C.fa[0][y]) {
            int z = C.move_up(y, C.dep[y]-C.dep[x]-1);
            adj[x].PB(z);
            x = z;
        }
        adj[x].PB(y);
    }

    int q[2*N], cz, op; vector<pair<LL, LL> > c;

    void dfs(int u) {
        for (auto v: adj[u]) {
            dfs(v); LL w = C.D[v] - C.D[u];
            if (u <= G.n) checkMax(z, f[u] + f[v] + w);
            checkMax(f[u], f[v] + w);
        }
        if (u > G.n) {
            c.clear();
            for (auto v: adj[u]) c.PB({f[v], G.D[v]});
            for (auto v: adj[u]) c.PB({f[v], G.D[v] + C.L[u]});
            cz = 0, op = 0; q[0] = 0; FOR(i, 1, SZ(c)) {
                while (cz <= op && c[i].se - c[q[cz]].se > C.L[u]/2) ++cz;
                if (cz <= op) checkMax(z, c[i].fi + c[q[cz]].fi + c[i].se - c[q[cz]].se);
                while (cz <= op && c[q[op]].fi - c[q[op]].se <= c[i].fi - c[i].se) --op;
                q[++op] = i;
            }
        }

        for (auto v: adj[u]) f[v] = 0;
        adj[u].clear();
    }

    VI T;

    void gao() {
        Rush T.PB(RD());

        UNQ(T, cmp); DWN(i, SZ(T)-1, 0) {
            int z = C.lca(T[i], T[i+1]);
            T.PB(z);
        }
        UNQ(T, cmp); top = 0; for (auto u: T) {
            while (top && C.lfn[sta[top]] < C.dfn[u]) --top;
            if (top) add_edge(sta[top], u); sta[++top] = u;
        }
        z = 0; dfs(T[0]); printf("%lld\n", z);
        f[T[0]] = 0; T.clear();
    }
} T;


int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    G.init(); C.init();
    Rush T.gao();
}