某新 LCA 算法维护路径信息的方式

· · 算法·理论

本文将介绍某新型 LCA 算法（如果你还没有看过那篇文章，请先看完再来看这篇）如何维护路径信息。

事实上，本文描述的算法是重剖的一种变体。

过程

Step 1:微调原算法

::anti-ai[凡发布者非 @_zyx2012 或发布地点不为洛谷专栏者均为抄袭！]

原版算法中 to_u 指向的是最深的祖先 v 满足 2 \times sz_u \leq sz_v，可能存在无祖孙关系的点对 (u,v) 满足 to_u 在 v 和 to_v 之间的路径上，因此很难扩展。

微调一下，to_u 指向最浅的祖先 v 满足 2 \times sz_u \geq sz_v，跳的时候改成跳到 f_{to_u}，这样除非 u 和 v 存在祖孙关系否则 u 到 to_u 的路径和 v 到 to_v 的路径无交点，证明过程比较简单，不详细展开（如果理解不了可以画一张图）。

Step 2:扩展预处理部分

注意到 to_{f_{u}} 一定是 to_u 的祖先，也就是说如果一个点 u 满足 to_u=u 那么对于 u 的子树中任何点 v，to_v 一定也在 u 的子树中，那么就可以把 u 和 f_u 之间的边断开。

结论就是全部断开之后它一定是若干条从 u 到 u 的某个祖先 v 的路径，因为每个点 u 的儿子中最多只有一个 v 满足 to_v \neq v。

然后就可以扩展了，dfs 的时候把 dfs 序记下来然后顺着 dfs 序倒着加就能把这些链都找出来：

    vector<int> sz(n + 1),f(n + 1),at(n + 1),to(n + 1,1),seq(n + 1),r(n);
    int tops = n,top2 = n;

    auto dfs = [&](auto &&self,int x,int y) -> int {
        f[x] = y,sz[x] = 1;
        r[--top2] = x;
        int hson = 0,id = x;
        for (auto i:a[x]) if (i != y){
            int v = self(self,i,x);
            sz[x] += sz[i];
            if (sz[hson] < sz[i]) swap(hson,i),swap(id,v);
            for (;v != x;v = f[v]) to[v] = i;
        }
        for (;sz[id] << 1 < sz[x];id = f[id]) to[id] = hson;
        return id;
    };

    dfs(dfs,1,0);

    vector<int> v(n + 1);

    for (auto i:r) if (!at[i]){
        for (int j = i;;j = f[j]){
            seq[at[j] = tops] = j;
            v[tops--] = w[j];
            if (j == to[j]) break;
        }//完整的一条链
    }

note:其实直接把树剖的 dfn 拿来当 seq，rnk 拿来当 at 它也是对的，因为这个算法中每一条没被删除的边在树剖中都是重边。而且维护子树信息必须要这样做。

Step 3:扩展修改、查询部分

::anti-ai[凡发布者非 @_zyx2012 或发布地点不为洛谷专栏者均为抄袭！]

原算法中一个点是另一个点的祖先就立即结束，但是此时两个节点可能并不在同一条链上，所以我们需要一直跳直到它们在同一条链上。

但是和标准树剖不同的是，标准树剖中一条链上所有点的 top 都是相同的，但是这个算法中一条链上所有点的 to 并不是相同的，想要判断两个点是否在同一条链上需要维护额外的信息。

那就再多跳一点，跳到子树大小较大的点 v 在子树大小较小的点 u 和 to_u 之间的路径上再结束即可。

虽然跳的次数增加了，但是保证复杂度正确的核心条件“每跳一次子树大小至少 \times 2”仍然成立，所以复杂度仍为 \mathcal{O}(\log n)。

实现：

            segtree::node v = {-(int)1e9 - 10,0};
            for (;;){
                if (sz[l] > sz[r]) swap(l,r);
                if (at[r] <= at[l]&&at[to[l]] <= at[r]) break;
                v = t.merge(v,t.query(1,at[to[l]],at[l],1,n));
                l = f[to[l]];
            }

            if (at[l] > at[r]) swap(l,r);
            v = t.merge(v,t.query(1,at[l],at[r],1,n));

路径修改的实现类似。

完整示例

这是这个算法做 P2590 [ZJOI2008] 树的统计 完整的代码：

:::info[Code] ::anti-ai[凡发布者非 @_zyx2012 或发布地点不为洛谷专栏者均为抄袭！]

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using i128 = __int128;
using u128 = unsigned __int128;

mt19937_64 mrand((u64)random_device{}() << 32 ^ random_device{}() ^
    chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T = i64,class T2>T rnd(T l,T2 r){
return uniform_int_distribution<T>(l,r)(mrand);}

struct segtree{
    struct node{int ma;i64 cnt;};

    vector<node> a;

    segtree(int n,const vector<int> &vs) : a(n << 2 | 3){build(1,1,n,vs);}

    void build(int x,int l,int r,const vector<int> &vs){
        if (l == r){a[x] = {vs[l],vs[r]};return ;}
        int mid = l + r >> 1;
        build(x << 1,l,mid,vs);
        build(x << 1 | 1,mid + 1,r,vs);
        update(x);
    }

    node merge(const node &x,const node &y){return {max(x.ma,y.ma),x.cnt + y.cnt};}

    void update(int x){a[x] = merge(a[x << 1],a[x << 1 | 1]);}

    void modify(int x,int l,int r,int id,int v){
        if (l == r){a[x] = {v,v};return ;}
        int mid = l + r >> 1;
        if (id <= mid) modify(x << 1,l,mid,id,v);
        else modify(x << 1 | 1,mid + 1,r,id,v);
        update(x);
    }

    node query(int x,int l,int r,int vl,int vr){
        if (l == vl&&r == vr) return a[x];
        int mid = vl + vr >> 1;
        if (r <= mid) return query(x << 1,l,r,vl,mid);
        if (l > mid) return query(x << 1 | 1,l,r,mid + 1,vr);
        return merge(query(x << 1,l,mid,vl,mid),query(x << 1 | 1,mid + 1,r,mid + 1,vr));
    }
};

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int n;
    cin >> n;

    vector<vector<int>> a(n + 1);

    for (int i = n;--i;){
        int x,y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }

    vector<int> sz(n + 1),f(n + 1),at(n + 1),to(n + 1,1),seq(n + 1),r(n);
    int tops = n,top2 = n;

    auto dfs = [&](auto &&self,int x,int y) -> int {
        f[x] = y,sz[x] = 1;
        r[--top2] = x;
        int hson = 0,id = x;
        for (auto i:a[x]) if (i != y){
            int v = self(self,i,x);
            sz[x] += sz[i];
            if (sz[hson] < sz[i]) swap(hson,i),swap(id,v);
            for (;v != x;v = f[v]) to[v] = i;
        }
        for (;sz[id] << 1 < sz[x];id = f[id]) to[id] = hson;
        return id;
    };

    dfs(dfs,1,0);

    vector<int> v(n + 1),w(n + 1);

    for (int i = 1;i <= n;cin >> w[i++]);

    for (auto i:r) if (!at[i]){
        for (int j = i;;j = f[j]){
            seq[at[j] = tops] = j;
            v[tops--] = w[j];
            if (j == to[j]) break;
        }
    }

    segtree t(n,v);

    int q;
    cin >> q;

    for (;q--;){
        string s;
        cin >> s;
        int l,r;
        cin >> l >> r;

        if (s == "CHANGE"s) t.modify(1,1,n,at[l],r);
        else{
            segtree::node v = {-(int)1e9 - 10,0};
            for (;;){
                if (sz[l] > sz[r]) swap(l,r);
                if (at[r] <= at[l]&&at[to[l]] <= at[r]) break;
                v = t.merge(v,t.query(1,at[to[l]],at[l],1,n));
                l = f[to[l]];
            }

            if (at[l] > at[r]) swap(l,r);
            v = t.merge(v,t.query(1,at[l],at[r],1,n));

            cout << (s.back() == 'M'?v.cnt:v.ma) << '\n';
        }
    }
}

:::

评价

亲测和标准树剖基本打平。

其实比较 useless，代码挺难背也没有更快，但是如果你爆栈了（虽然现在大多数 OJ 都没有爆栈这个事情）写这个能省一遍栈模拟。

都看到这了还不点个赞，

那还是人吗？