有关静态树链问题

ICE__LX · 2025-01-25 18:14:44 · 算法·理论

开始前先进行一个全民投票吧！

投票：遇到静态树链问题，你会选择（点击选项进行投票）：
1、直接树链剖分！
2、其他在线算法？
3、考虑离线算法。
4、本蒟蒻不会……

简介

本文主要讨论静态的树链问题。树链问题，可以看作树上的区间问题，这个区间可以看作一个结点 u 到另一个结点 v 所经最短路径形成的序列。这种问题大多需要用树链剖分来解决，但树链剖分会在解决对应区间问题的数据结构上增加一个 \log，这无疑会大大增加算法的常数压力，因此本文将在静态树链问题上讨论其他解法。

由于作者能力有限，因此仅提供了三道例题，而且知道的解法并不多，因此本文的代码量十分饱满，理论方面的讲解对新人比较不友好，也希望大家能够提出其他高效的思路和建议。

例题一：树链求和

解法一：树链剖分

思路非常简单，就是纯粹的树链剖分，由于没有修改操作，可以直接跑前缀和，然后以 O(1) 的复杂度完成每次子区间查询，单次查询的时间复杂度为 O(\log n)。

这种做法的时间复杂度主要看查询的数据结构，在遇到复杂的静态树链问题上并不吃香，很容易被卡常。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define I_love_Foccarus 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;
const int inf = INT_MAX;
inline int read() { //浓缩后的快读    
    int x=0,f=1,ch=getchar();
    while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    I_love_Foccarus x*f;
}
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;
}
int c[N] , a[N];
int sz[N] , w[N] , top[N] , dfn[N] , dfm[N] , dep[N] , fa[N], vis;
void dfsw(int u,int father) { //求重链 
    sz[u] = 1;
    dep[u] = dep[father] + 1;
    for(int i = head[u] ; i ; i = edge[i].nex) {
        int v = edge[i].act;
        dfsw(v , u);
        sz[u] += sz[v];
        if(sz[v] > sz[w[u]]) w[u] = v;
    }
}
void dfs(int u , int ftop) { //树链剖分 
    dfn[u] = ++vis , dfm[vis] = u , top[u] = ftop;
    if(w[u]) dfs(w[u] , ftop);
    for(int i = head[u] ; i ; i = edge[i].nex) {
        int v = edge[i].act;
        if(v == w[u]) continue;
        dfs(v , v);
    }
}
int query(int x , int y) { //查询 
    int ans = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x , y);
        ans += c[dfn[x]] - c[dfn[top[x]] - 1]; //统计子区间和 
        x = fa[top[x]];
    }
    if(dfn[x] < dfn[y]) swap(x , y);
    ans += c[dfn[x]] - c[dfn[y] - 1];
    I_love_Foccarus ans;
}
signed main() {
    int n , root;
    in(n);
    rep(i , 1 , n)in(a[i]);
    rep(i , 1 , n) {
        in(fa[i]);
        if(fa[i] != i)eadd(fa[i] , i);
        else root = i;
    }
    dfsw(root , 0);
    dfs(root , 0);
    rep(i , 1 , n)c[i] = c[i - 1] + a[dfm[i]]; //前缀和初始化 
    int q;
    in(q);
    while(q--){
        int u , v;
        in(u) , in(v);
        printf("%d\n",query(u , v));
    }
    I_love_Foccarus 0;
}

解法二：容斥原理（树上差分）

不难发现，查询的内容可减，因此可以先通过一轮 dfs 求出每个结点到根结点的路径形成的序列的序列和，用一个数组 f 储存下来。

然后举个例子，如图，查询 3,5：

不难发现 f_{\operatorname{LCA}(u,v)} 被计算了两次，需要减去，然而 \operatorname{LCA}(u,v) 也在查询的树链内，因此还需将 \operatorname{LCA}(u,v) 的权值加上，从而得出结点 u 到结点 v 所经最短路径形成的序列的序列和为 f_u+f_v- 2f_{\operatorname{LCA}(u,v)}+a_{\operatorname{LCA}(u,v)}，其中 a 表示点权。

而 a_{\operatorname{LCA}(u,v)} 又可以由 f_{\operatorname{LCA}(u,v)}-f_{fa_{\operatorname{LCA}(u,v)}} 得出，其中 fa 表示该结点的父亲结点。因此也可以写作 f_u+f_v- f_{\operatorname{LCA}(u,v)}-f_{fa_{\operatorname{LCA}(u,v)}}，特殊的，如果 \operatorname{LCA}(u,v) 为根结点，那么查询的值就应为 f_u+f_v- f_{\operatorname{LCA}(u,v)}，因为根结点没有父亲结点。

这种做法需要求 LCA，因此单次查询的时间复杂度同样为 O(\log n)。

虽然这种思路很简单，代码也很好写，但是处理的问题必须满足可减，这就是它的局限性。面对复杂的静态树链问题，这种做法往往不会被采用。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define I_love_Foccarus 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;
const int inf = INT_MAX;
inline int read() { //浓缩后的快读    
    int x=0,f=1,ch=getchar();
    while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    I_love_Foccarus x*f;
}
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;
}
int n , q;
int fa[N][21] , d[N] , f[N];
void dfs(int u,int dep) { //倍增 LCA 初始化 
    d[u] = dep;
    for(int i = head[u] ; i ; i = edge[i].nex){
    int v = edge[i].act;
    f[v] += f[u]; //记录该结点到根结点的权值和 
    dfs(v , dep + 1);   
    }   
}
int LCA(int x , int y) { //倍增 LCA 
    if(d[x] < d[y])swap(x , y);
    for(int i = 20 ; i >= 0 ; i--) {
        int v = fa[x][i];
        if(d[v] < d[y])continue;
        x = v;
    }
    if(x == y)return x;
    for(int i = 20 ; i >= 0 ; i--) {
        if(fa[x][i] == fa[y][i])continue;
        x = fa[x][i];
        y = fa[y][i];
    }
    I_love_Foccarus fa[x][0];
}
signed main() {
    int root;
    in(n);
    rep(i , 1 , n)in(f[i]);
    rep(i , 1 , n) {
        in(fa[i][0]);
        if(fa[i][0] != i)eadd(fa[i][0] , i);
        else root = i , fa[i][0] = 0; //让根结点指向权值为零的数 
    }
    dfs(root , 1);
    for(int i = 1 ; i <= 20 ; i++) { //倍增 LCA 初始化 
        for(int j = 1 ; j <= n ; j++) {
            int v = fa[j][i - 1];
            fa[j][i] = fa[v][i - 1];
        }
    }
    in(q);
    while(q--){
        int u , v;
        in(u) , in(v);
        int lca = LCA(u , v);
        printf("%d\n",f[u] + f[v] - f[lca] - f[fa[lca][0]]); //容斥原理求解 
    }
    I_love_Foccarus 0;
}

解法三：Tarjan

类似于 Tarjan 离线求 LCA，但与之不同的是，我们需要用带权并查集进行维护。这种带权并查集的权值合并比较特殊，每个结点的权值不会加到父结点那里去，而是与之相反，将父结点的权值加到自身，这里可以看作权值合并的逆操作，而且这种合并可以路径压缩。注意这种操作不应将根结点的权值合并，因为每次查询都一定会重复合并到其根结点，因此最好的办法就是在路径压缩时不合并根结点，然后在处理答案时再分类讨论。

接下来来讨论处理答案。
处理答案需要满足查询的两个结点都已经与其 LCA 合并，因此需要枚举它们的 LCA，可以通过 Tarjan 离线求出 LCA，然后打下标记，在回溯到对应 LCA 时再进行处理。

由于查询的两个结点存在三种情况，现进行分类讨论。
设查询的两个结点为 u,v，那么有以下情况：