严格 log n Link-Cut Tree 正篇

未分类

---

为了保持严格 $O(\log n)$ 的复杂度，我们首先要舍弃原来简单暴力的 Expose 方法，然后再舍弃均摊复杂度的 splay ，换上两个严格 $O(\log n)$ 的策略。第一个问题是如何 Expose ，我们用已知的方法——轻重边树链剖分来处理。我们每次 expose(x) 的时候将路径上的轻边变为实边，进行操作过后再调用 conceal(x) 来把路径上的轻边恢复为虚边，由于一条路径上只有 $O(\log n)$ 条轻边，因此理想的复杂度应该可以做到 $O(\log n)$ 。

注：本文的边有四种：实边(solid)，虚边(dashed)，重边(heavy)，轻边(light)（知道 link-cut tree 和树链剖分的大家应该都熟悉这些概念了），实/虚 是 link-cut tree 中的概念，是我们维护的对象，重/轻 是轻重边树链剖分中的概念，是我们分析的工具。
注2：为了区分树上的节点和 LCT 节点，树上的节点用 $u,v,w$ 表示， LCT 中的节点用 $x$ 表示（代码中除外）。

处理轻边

若一条边 $(u,v)$ 满足 $2size(v)\leq size(u)$ ，则称其为轻边（这一定义和轻重边树链剖分中是基本一致的）。为了判定轻边我们需要一个点的 $size$ ，而 link-cut tree 有一个重要的操作就是改变树的根，为了支持这个操作，我们定义 $wt(u)$ 为：

$$wt(u)=\begin{cases}size(u) & \text{if $u$ have no solid son} \\ size(u)-size(v) & \text{if $u$ have solid son $v$}\end{cases}$$

总的来说就是 $u$ 的虚儿子的子树大小之和加一，注意在把当前的根 $r$ 切换到新根 $u$ 的时候我们只需要先 expose(u) ，然后再把根换到 $u$ 上，此时 $path(r,u)$ 上的点的 $wt$ 并不会改变，这样就可以维护 $wt$ 了。

通过 $wt(u)$ 我们可以求出 $size(u)=\sum_{w\in path(u,tail(u))} wt(w)$ 。
于是对于有实儿子 $v$ 的点 $u$ 定义 $f(u)=size(u)-2size(v)=wt(u)-\sum_{w\in path(v,tail(v))} wt(w)$ ，若 $f(u)\geqslant 0$ 说明 $(u,v)$ 是轻边。

expose(x) 的实现和之前差不多，然后 conceal(x) 的时候只需要在实链中不断寻找最大的 $f(u)$ ，如果不小于零就标为轻边并继续即可。于是我们需要支持链查询区间最大的 $f(u)$ 。

为了支持查询，我们对一个 LCT 节点 $x$ （所代表的是树上的节点 $u$） 维护：
$sum_x$ - 子树的 $wt$ 和
$f(x)=wt(u)-wtsum(x.rc)$ （和 $f(u)$ 略有区别）
$maxf(x)=\max(maxf(x.lc)-wtsum(x.rc)-wt(u),f(x),maxf(x.rc))$
为了支持区间翻转还要维护 $f(x),maxf(x)$ 翻转后的版本 $f'(x),maxf'(x)$ ，略去。

即可查询在平衡树的根节点查询到子树最大的 $f(u)$ 。（这里我的实现和论文有区别，如果有错误求指正）

除了寻找轻边以外，我们在断掉轻边的时候还需要找到是否有需要重新连接的重边，为了找到这些重边，我们可以用平衡树维护和点 $u$ 相邻的所有实链（自己所在的那条除外）的 $wt$ ，取出其中权值最大的一条即可。

其他部分的实现

所有的平衡树都使用之前介绍过的 Biased Search Tree ，取 $w_x=wt(x)$ 。

为了避免麻烦用了C++的bind……凑合看个意思就行了（然而有的变量可能打错了qaq，如果看到的话求指正）

void update(Node u) {
    //update the information from root to u
}
Node splice(Node v) {
    int x = fa[v.head];
    Node p, q, u = lct[x]; int a, b;
    bind(p, q, a, b) = split(u);
    u.wt -= v.wtsum; update(u);
    del(v, x);
    if (q != null) {
        fa[q.head] = x; fa[q.head] = b;
        u.wt += q.wtsum; update(u);
        ins(q, x);
    }
    u = concat(u, v, fc[v.head]);
    return p == null ? u : concat(p, u, a);
}
Node expose(int x) {
    Node p, q;
    int a, b;
    Node u = lct[x];
    bind(p, q, a, b) = split(x);
    if (q != null) {
        fa[q.head] = x; fc[q.head] = b;
        u.wt += q.wtsum; update(u);
        ins(q, x);
    }
    u = p == null ? u : concat(p, u, a);
    while (fa[u.head] != 0) u = splice(u);
    return p;
}
void slice(Node p) {
    int x = getLightEdge(u);
    Node q, u = lct[x]; int a, b;
    bind(p, q, a, b) = split(u);
    p = p == null ? u : concat(p, u, a);
    fa[q.head] = x; fc[q.head] = b;
    u.wt += q.wtsum; update(u);
    Node v = getHeavySon(x);
    if (2 * v.wtsum > u.wt) {
        u.wt -= v.wtsum; update(u);
        del(v, x);
        concat(p, v, fc[v.head]);
    }
    ins(q, x);
    return q;
}
void conceal(Node p) {
    while (getLightEdge(p) != null) {
        p = slice(p);
    }
    int x = u.tail; Node u = lct[x];
    Node v = getHeavySon(x);
    if (v != null && 2 * v.wtsum > p.wt) {
        bind(p, q, a, b) = split(x); //q == null
        u.wt -= v.wtsum; update(u);
        del(v, x);
        u = concat(u, v, fc[v.head]);
        if (p != null) concat(p, u, x);
    }
}

复杂度证明

我觉得 $O(\log^2 n)$ 的 bound 应该不需要证明了，对 $O(\log n)$ 条轻边进行了 $O(\log n)$ 次操作。

splice: split(u) 会产生 $rank(t)-rank(u)\geqslant rank(t)-rank(v)$ 的代价（ $t$ 为 $u$ 一开始所在的实链），由于在一次操作后 $wt(v')=wt(t)$ ，所以总的复杂度是 $O(\log n)$ 的；concat(u,v) 和 concat(p,u) 会产生 $O(1)$ 和 $O(rank(t)-(rank(u)-rank(v)))=O(rank(t)-rank(v))$ （由于 $(u,v)$ 是轻边所以 $O(size(u)-size(v))=O(size(v))$ ），之后分析同 split ； ins 的复杂度由于 q.head 是 $u$ 的重儿子所以 $O(\log (wt(u)/wt(q))=O(1)$ ； del 的复杂度是 $O(rank(u)-rank(v))\leqslant O(rank(t)-rank(v))$ ，分析同前。

expose: 没什么可分析的，只有 $O(1)$ 次操作。

slice: getLightEdge 和 split 的复杂度都是 $O(rank(p)-rank(u))$ ，一起分析，由于 $u$ 的实儿子是它的轻儿子， $O(rank(u))=O(rank(q))$ ，因此复杂度就是 $O(rank(p)-rank(q))$ ，之后递归到 $q$ ，总复杂度就是 $O(\log n)$ 的；两次 concat 的复杂度都是 $O(rank(p)-rank(u))\geqslant O(rank(p)-rank(q))$ 的，和 split 同理； del 的复杂度由于 $v.head$ 是 $u$ 的重儿子所以 $O(\log (wt(u)/wt(v))=O(1)$ ； ins 的复杂度是 $O(rank(u)-rank(q))\leqslant O(rank(p)-rank(q))$ ，分析同前。

conceal: 同 expose 。

综上，由于各处复杂度都是严格的，这里描述的算法的时间复杂度是严格 $O(\log n)$ 的。