某島

… : "…アッカリ~ン . .. . " .. .
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();
}