Tarjan 算法在静态树链问题上的应用

Kei__ · 2025-11-22 05:58:43 · 算法·理论

静态树链问题

树链通常指树上两点间的最短路径形成的点集或边集，而静态树链问题就是没有修改操作，只进行查询的树链问题。

静态树链问题涉及最近公共祖先（LCA），比较常用做法就是倍增 LCA 与树剖 LCA，两者的时间复杂度均为 O(\log n)，区别是前者更好理解，而后者的常数则更小，复杂度更优秀。而本文期望以接近线性的时间复杂度，将采用一种比较冷门的算法离线求 LCA，后文会进行具体讲述。

通常，静态树链问题通常具有可减性与可合并性这两种性质中的一个或是都有。

举个例子，静态树链求和就是一个满足可减性与可合并性的静态树链问题，常见的做法就是，预处理每个节点到根的树链和，然后用树上差分求解。当然也可以用树上倍增或树链剖分配合前缀和实现，两者都基于可合并性，而后者由于使用前缀和还依赖于可减性。

本文提及的算法依赖与可合并性，因此不提及可减性静态树链问题。

Tarjan 算法离线求 LCA

Tarjan 算法的具体思路就是，将每个查询离线下来，标记在树上的点上，然后进行一遍 dfs 计算出所有查询的结果，这是一个典型的离线算法。

该算法的暴力思路就是，枚举每个节点 x 作为候选 LCA，遍历该子树，找到子树内的两个节点，满足两点属于同一次查询，然后更新查询的结果，查询结果为深度最低的 x。

很显然，这种做法是 O(qn^2)，不能接受，接下来考虑如何优化。

我们反过来思考，把树边全部断开，然后按后序遍历的顺序，逐一将每个点与其父亲节点的边连上。在连接过程中，如果查询的两点 u,v 处于同一个连通块，那么连通块最高点就为它们的 LCA。

那如果每合并一次就检查所有查询的两点是否连通，我们的复杂度就成了 O(qn)，还不够。

假设我们遍历到了一个节点 u，离线的信息记录与其相关的查询，我们也就知道了另一个点 v。如果 v 已经访问过，那么我们可以通过反证法来证明：u 与 v 的 LCA 是 v 在连通块中所能达到的最高点。

如果 u 与 v 的 LCA 不是 v 在连通块中所能达到的最高点，那么 v 在连通块中所能达到的最高点的深度就低于或高于 LCA。如果低于 LCA，那么就不可能访问到 u 矛盾。如果高于 LCA，那么节点 u 与其父亲节点间的边就已经连上，同样矛盾。

所以，u 与 v 的 LCA 是 v 在连通块中所能达到的最高点。

我们可以用并查集维护每个节点在连通块所能达到的最高点，同时采用路径压缩优化。复杂度为 O(n+q\alpha(n))，接近线性。

Tarjan 算法在静态树链问题上的应用

由于要维护树链信息，我们需要用带权并查集进行维护每个节点到能达到的最高点的树链信息。因此这种带权并查集的权值合并比较特殊，每个结点的权值不会加到父结点那里去，而是与之相反，将父结点的权值加到自身，这里可以看作权值合并的逆操作，而且这种合并可以路径压缩。

注意这种操作不应将根结点的权值合并，因为每次查询都一定会重复合并到其根结点，因此最好的办法就是在路径压缩时不合并根结点，然后在处理答案时再分类讨论，而如果仅仅是维护树边权信息则不需要考虑。

因此，带权并查集在处理点权树链时维护的信息有两种情况：对于并查集的非根元素，其储存自身到根节点且信息不包含根节点的树链信息，而根节点则是只储存了自身的节点信息。

那么我们就通过带权并查集维护了每个节点到连通快最高点的树链信息，对于每次查询只需将 u,v 记录的信息合并即可。因此在处理答案的时候需要保证 u,v 处于同一个连通块，而求出 LCA 时，u,v 尚未合并成一个连通块，故打下标记，在回溯到其对应 LCA 时再进行处理。

由于查询时 u,v 和他们的 LCA 的位置关系存在三种情况，可以基于维护点权信息现进行分类讨论：

于是我们可以基于 O(n+q\alpha(n)) 的复杂度解决非强制在线的可合并性静态树链问题。

静态树链最值

最值查询满足可减性与可重叠性，因此不需要像上述思路那样考虑得那么麻烦，可以带权并查集合并时可以合并根节点，而且不需要进行分类讨论，直接将信息合并即可。因此细节处理方面比较简单，写起来也比较流畅。

::::success[参考代码与注释]

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define I_love_ARIS return
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define deap(i,a,b) for(int i=a;i>=b;i--)
#define in(a) a=read()
#define fi first
#define se second
const int N = 1e5 + 5 , maxn = 3e6 + 5;
const int inf = INT_MAX;
inline int read() {
    int x = 0 , ch = getchar() , f = 0;
    while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();
    while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();
    I_love_ARIS f ? -x : x;
}
struct Edge { 
    int act , nex;
} edge[N];
int head[N] , eid;
void eadd(int u , int v) {
    edge[++eid].act = v , edge[eid].nex = head[u] , head[u] = eid;
}
vector< pair< pair<int , int> , int > >solve[maxn]; //LCA 标记 
vector< pair<int , int> >Q[maxn]; //离线储存查询 
int n , q , fa[N] , vis[N] , d[N] , a[N] , ans[maxn];
int find(int x) { 
    if(fa[x] != x){ //带权并查集合并 
        int root = find(fa[x]);
        d[x] = min(d[x] , d[fa[x]]); //将父亲结点权值合并到自身 
        fa[x] = root; 
    }
    I_love_ARIS fa[x];  
}
void Tarjan(int u) { 
    fa[u] = u , vis[u] = 1 , d[u] = a[u];  
    for(int i = head[u] ; i ; i = edge[i].nex) {
        int v = edge[i].act;
        Tarjan(v);
        fa[v] = u; //可以直接合并 
    }
    for(auto v:Q[u]){ //求 LCA 和打标记 
        if(!vis[v.fi])continue; 
        solve[find(v.fi)].push_back(make_pair(make_pair(u , v.fi) , v.se));
    }
    for(auto v:solve[u]){ //处理每次询问   
        find(v.fi.fi) , find(v.fi.se); //进行权值合并   
        ans[v.se] = min(d[v.fi.fi] , d[v.fi.se]); // 合并答案
    }
}
signed main() {
    int root;
    in(n);
    rep(i , 1 , n)in(a[i]);
    rep(i , 1 , n) {
        int f;
        in(f);
        if(f != i)eadd(f , i);
        else root = i;
    }
    in(q);
    rep(i , 1 , q) { //离线记录每次询问  
        int u , v;
        in(u) , in(v);
        Q[u].push_back(make_pair(v , i));
        Q[v].push_back(make_pair(u , i));
    }
    Tarjan(root); 
    rep(i , 1 , q) printf("%d\n",ans[i]);
    I_love_ARIS 0;
}

::::

静态树链最大子段和

此题就需要完全按照上述思路进行了。

不难发现，最大子段和满足可合并，用带权并查集维护四个信息，分别为最大子段和、树链和、最大前缀和、最大后缀和，方便合并。

为了方便，我们用 a,b,c,d 分别来表示最大子段和、树链和、最大前缀和、最大后缀和，u,v 表示合并的左右两个信息，f 表示合并后的信息。

1. 最大子段和合并：
   有三种情况，如图：
   
   对这三种情况取最大值就是合并后的最大子段和，查询时的合并是将最大后缀和合并，分类讨论判断是否需要同 LCA 一同合并，如果需要，可将两个最大后缀和与 0 取最大值，因为也可以选择不之合并。

2. 树链和合并：
   直接将两个树链和相加即可。

3. 最大前缀和合并：
   有两种情况，第一种最大前缀和就是 c_u，第二种是 b_u+c_v，然后对两种情况取最大值。

4. 最大后缀和合并：
   同最大前缀和合并一样，有两种情况，第一种是 d_v，第二种是 b_v+d_u，对两种情况取最大值即可。

综上可以得出：