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 …）

void Link(int x, int y){
    if (Root(x) == Root(y)){
        puts("-1");
    }
    else {
        Evert(x), Splay(x), p[x] = y, Access(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;
        //Update(x);
    }
}

。再以此题为例。。

对于得到一条路径的做法，先 一个 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 的 1、2、3 。。三个难题。。(> <)。。。。 ） --- UPD --- 现在的搞法。

External link :

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

Posted by xiaodao
Category: 日常
Tags: 动态树