某島

… : "…アッカリ~ン . .. . " .. .
September 9, 2011

HDU 4010. Query on The Trees

Brief description :

… 動態維護一組森林,要求支持以下操作:

  • Link(a, b) 如果 a,b 不在同一顆子樹中,則通過在 a,b 之間連邊的方式,連接這兩棵子樹。
  • Cut(a, b) 如果 a,b 在同一顆子樹中、且 a != b,則將 a 視為這棵子樹的根之後,切斷 b 與其父親結點的連接。
  • Modify(w, a, b) 如果 a, b 在同一顆子樹中,則將 a, b 之間路徑上所有的點權增加 w。
  • Query(a, b) 如果 a, b 在同一顆子樹中,返回 a, b 之間路徑上點權的最大值。

Analysis :

。。Link-Cut Tree 的核心操作 。。Access()。。(只有調用這個過程會改變邊的虛實關係 (Solid / Dashed) )。。
。。介於 Splay 保存路徑的特殊方式,通常。。要將需要操作的節點 Splay() 到根(以獲得其對整棵子樹的完整信息)之後才可以對其進行進一步的操作 .. .
這裡需要引入 rev 標記進行修改樹根的操作(只存在於作用於無根樹的題目中,例如 SPOJ 4155. OTOCI …)

。再以此題為例。。

對於得到一條路徑的做法,先 一個 Access() 過程訪問其中的一個點,再通過 一個修改的 Access() 過程 訪問另一個點,
在第二次 Access() 的最後階段會通過 p[] 指針得到這兩點之間的 LCA … (Orz)
(。。交換 Access() 的順序不影響。。)

然後使用 .. max(w1[rx], w0[x], w1[y]) .. 就可以得到這條路徑上點權的最大值。(如果是邊權系列問題,中間的 w0[x] 會消失。。。。 )

void Query(int x, int y){
    if (Root(x) != Root(y)){
        puts("-1");
    }
    else {
        Access(y); y = 0; do{
            Splay(x), Release(x); if (!p[x]) OT(max(w1[rx], w0[x], w1[y]));
            rt[rx] = true, rt[rx = y] = false, Update(x);
            x = p[y = x];
        } while (x);
    }
}

對於修改操作,我們需要再引入一個 delay 標記。

inline void Inc(int x, int d){
    if (x == 0) return;

    w0[x] += d, w1[x] += d, delay[x] += d;
}

於是得到 Modify() 的過程。。。

void Modify(int x, int y, int w){
    if (Root(x) != Root(y)){
        puts("-1");
    }
    else {
        Access(y); y = 0; do{
            Splay(x), Release(x); if (!p[x]) Inc(rx, w), w0[x] += w, Inc(y, w);
            rt[rx] = true, rt[rx = y] = false, Update(x);
            x = p[y = x];
        } while (x);
    }
}

。。各種維護就可以了。。。。

( .. HDOJ Rank I . 593ms 達成 .. )

Further discussion :

Link-Cut Tree 的先修技能是 Splay,推薦入門題。。
SGU 187. Twist and whirl — want to cheat .. .

之後做這題之前一定要有同時維護向上向下傳遞的經驗。
(自頂向下下放 (Release()) 的標記 (rev, delay),和自底向上維護 (Update()) 的關鍵字 (w0, w1))。。

可以參見那兩道 S 級數據結構 .. .
NOI 2005. 維修數列 。。和。。
SPOJ 1557. Can you answer these queries II。。

額。。。補充一些問題,
首先,各個子過程需要做到 ———— 各司其職。。
這裡的含義是盡量不要做額外「畫蛇添足」的事情,例如 。。

  • Access() 操作之後緊接著 Splay() 到根節點 (直接固化在 Access() 裡面)。。。。。 不必要。。。你可以通過 調用 _Access(x) (加前綴下劃線表示一個返回版本。。)結束然後返回其最後訪問到的結點(也就是此時的樹根。)。。對這個結點進行操作即可。。
  • Update() 過程裡面嵌一個 Release() 。。。(這個。。因為此題中維護的 w1 信息,左右子樹是否交換對其不造成影響。。顯然可以去掉。。( GSS 6 )。。)
  • Rotate() 操作裡面不停的 Update(), Release(), Update(), Release() 。。.. .
  • .

(額,最後說一下由於我一直使用單旋 Splay。。 Splay() 過程被寫的只有一行。。沒有對旋轉方向的判斷所以是需要寫一部分標記下放到 Rotate() 裡面的。。)
(。。Unsolved Problem .. 。。)

如果你是「數據結構控」。。對這幾個非常感興趣,我猜你可能會喜歡這個。。.[挖坑]動態樹與樹鏈剖分.. .
我收集了一些資源 (Resource) 和習題 (Exercise)

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_C(i, a, b) for (int b____=int(b),i=int(a);i<b____;++i)
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
#define DO(n) while(n--)
#define DO_C(n) int n____ = n; while(n____--)

template<class T> inline void RD(T &x){char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';}
inline int RD(){ int x; RD(x); return x;}
template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}
template<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}
template<class T> inline void OT(const T &x){printf("%d\n", x);}
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}

/*--------*/

const int N = 300009, M = 2 * N;

int l[N], r[N], p[N], w0[N], w1[N], delay[N], rev[N]; bool rt[N];
// Link-cut tree
int hd[N], nxt[M], a[M], b[M];
// Adjacent list
int n;

#define lx l[x]
#define rx r[x]

// private:

inline void Inc(int x, int d){
    if (x == 0) return;
    w0[x] += d, w1[x] += d, delay[x] += d;
}

inline void Release(int x){
    if (x == 0) return;

    if (rev[x]){
        swap(lx, rx);
        rev[lx] ^=1, rev[rx] ^=1;
        rev[x] = 0;
    }

    if (delay[x]){
        Inc(lx, delay[x]), Inc(rx, delay[x]);
        delay[x] = 0;
    }
}

inline void Update(int x){
    w1[x] = max(w0[x], w1[lx], w1[rx]);
}

inline void Set(int l[], int y, int x){
    l[y] = x, p[x] = y;
}

#define z p[y]
inline void Rotate(int x){
    int y = p[x];

    if (!rt[y]) Release(z), Set(y == l[z] ? l : r, z, x);
    else p[x] = z;

    Release(y), Release(x);

    if (x == l[y]) Set(l, y, rx), Set(r, x, y);
    else Set(r, y, lx), Set(l, x, y);

    if (rt[y]) rt[y] = false, rt[x] = true;
    Update(y);
}

inline void Splay(int x){
    while (!rt[x]) Rotate(x);
}

inline int Access(int x){
    int y = 0; do{
        Splay(x), Release(x);
        rt[rx] = true, rt[rx = y] = false, Update(x);
        x = p[y = x];
    } while (x);
    return y;
}

inline int Root(int x){
    for (x = Access(x); Release(x), lx; x = lx);
    return x;
}

inline void Evert(int x){
    rev[Access(x)] ^= 1;
}

// public:

void Query(int x, int y){
    if (Root(x) != Root(y))
        puts("-1");
    else {
        Access(y); y = 0; do{
            Splay(x), Release(x); if (!p[x]) OT(max(w1[rx], w0[x], w1[y]));
            rt[rx] = true, rt[rx = y] = false, Update(x);
            x = p[y = x];
        } while (x);
    }
}

void Link(int x, int y){
    if (Root(x) == Root(y))
        puts("-1");
    else {
        Evert(x), Splay(x), p[x] = y, Access(x);
    }
}

// Set y as a root, Cut the connection between x and p[x] ..
void Cut(int y, int x){
    if (x == y || Root(x) != Root(y))
        puts("-1");
    else {
        Evert(y), Splay(y), Access(x), Splay(x);
        p[lx] = p[x], rt[lx] = true, p[x] = lx = 0;
    }
}

void Modify(int x, int y, int w){
    if (Root(x) != Root(y))
        puts("-1");
    else {
        Access(y); y = 0; do{
            Splay(x), Release(x); if (!p[x]) Inc(rx, w), w0[x] += w, Inc(y, w);
            rt[rx] = true, rt[rx = y] = false, Update(x);
            x = p[y = x];
        } while (x);
    }
}

#define v b[i]
inline void dfs(int u = 1){
    for(int i=hd[u];i;i=nxt[i]) if (!p[v]){
        p[v] = u, dfs(v);
    }
}

int main(){
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    while (scanf("%d", &n) != EOF){
        // Initializing Phase
        FOR_C(i, 2, n << 1){
            RD(a[i], b[i]), a[i|1] = b[i], b[i|1] = a[i];
            nxt[i] = hd[a[i]], hd[a[i]] = i; ++i;
            nxt[i] = hd[a[i]], hd[a[i]] = i;
        }

        REP_1(i, n) RD(w0[i]), rt[i] = true;
        p[1] = -1, dfs(), p[1] = 0;

        //Interaction Phase
        int a, b, cmd; DO_C(RD()){
            RD(cmd, a, b); if (cmd == 1) Link(a, b);
            else if (cmd == 2) Cut(a, b);
            else if (cmd == 3) Modify(b, RD(), a);
            else Query(a, b);
        }

        puts("");

        // Rececling ...
        RST(hd, p, l, r, delay, rev);
    }
}



下一階段的任務。。我覺得動態樹我還沒弄明白。。還想在花一段時間。。
先打算先寫一下動態樹的那個「正當用途」 ———— 優化網路流。。
之後。。
我就去解決掉 fhq 的 123 。。三個難題。。(> <)。。。。 ) --- UPD --- 現在的搞法。

External link :

http://acm.hdu.edu.cn/showproblem.php?pid=4010