浅谈静态树链问题
开始前先进行一个全民投票吧！投票：遇到静态树链问题，你会选择（点击选项进行投票）：
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;
int head , eid;
void eadd(int u , int v) {
edge[++eid].act = v , edge.nex = head , head = eid;
}
int c , a;
int sz , w , top , dfn , dfm , dep , fa, vis;
void dfsw(int u,int father) { //求重链
sz = 1;
dep = dep + 1;
for(int i = head ; i ; i = edge.nex) {
int v = edge.act;
dfsw(v , u);
sz += sz;
if(sz > sz]) w = v;
}
}
void dfs(int u , int ftop) { //树链剖分
dfn = ++vis , dfm = u , top = ftop;
if(w) dfs(w , ftop);
for(int i = head ; i ; i = edge.nex) {
int v = edge.act;
if(v == w) continue;
dfs(v , v);
}
}
int query(int x , int y) { //查询
int ans = 0;
while(top != top) {
if(dep] < dep]) swap(x , y);
ans += c] - c] - 1]; //统计子区间和
x = fa];
}
if(dfn < dfn) swap(x , y);
ans += c] - c - 1];
I_love_Foccarus ans;
}
signed main() {
int n , root;
in(n);
rep(i , 1 , n)in(a);
rep(i , 1 , n) {
in(fa);
if(fa != i)eadd(fa , i);
else root = i;
}
dfsw(root , 0);
dfs(root , 0);
rep(i , 1 , n)c = c + a]; //前缀和初始化
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;
int head , eid;
void eadd(int u , int v) {
edge[++eid].act = v , edge.nex = head , head = eid;
}
int n , q;
int fa , d , f;
void dfs(int u,int dep) { //倍增 LCA 初始化
d = dep;
for(int i = head ; i ; i = edge.nex){
int v = edge.act;
f += f; //记录该结点到根结点的权值和
dfs(v , dep + 1);
}
}
int LCA(int x , int y) { //倍增 LCA
if(d < d)swap(x , y);
for(int i = 20 ; i >= 0 ; i--) {
int v = fa;
if(d < d)continue;
x = v;
}
if(x == y)return x;
for(int i = 20 ; i >= 0 ; i--) {
if(fa == fa)continue;
x = fa;
y = fa;
}
I_love_Foccarus fa;
}
signed main() {
int root;
in(n);
rep(i , 1 , n)in(f);
rep(i , 1 , n) {
in(fa);
if(fa != i)eadd(fa , i);
else root = i , fa = 0; //让根结点指向权值为零的数
}
dfs(root , 1);
for(int i = 1 ; i <= 20 ; i++) { //倍增 LCA 初始化
for(int j = 1 ; j <= n ; j++) {
int v = fa;
fa = fa;
}
}
in(q);
while(q--){
int u , v;
in(u) , in(v);
int lca = LCA(u , v);
printf("%d\n",f + f - f - f]); //容斥原理求解
}
I_love_Foccarus 0;
}解法四：树上倍增
就像求倍增 LCA，在记录成倍增长的父结点信息的同时合并权值，然后在倍增求 LCA 的过程中将权值合并，也就是把查询的要合并的两条链拆解成若干个二进制片段，然后合并。信息不可重复，需要去重，为了权值避免权值重复合并，合并记录的信息不能计入成倍跳到了的结点的权值，然后在查询时加上漏掉的 LCA 的点权。
时间复杂度为 \(O(q\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 , maxn = 1e6 + 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;
int head , eid;
void eadd(int u , int v) {
edge[++eid].act = v , edge.nex = head , head = eid;
}
vector< pair< pair<int , int> , int > >solve; //LCA 标记
vector< pair<int , int> >Q; //离线储存查询
int n , q , fa , vis , d , a , ans;
int find(int x) { //带权并查集合并
if(fa != fa]){ //如果父亲结点不是根结点
int root = find(fa);
d += d]; //将父亲结点权值合并到自身
fa = root; //路径压缩
}
I_love_Foccarus fa;
}
void Tarjan(int u) { //Tarjan 离线求树链和
fa = u , vis = 1 , d = a;//结点初始化
for(int i = head ; i ; i = edge.nex) {
int v = edge.act;
Tarjan(v);
fa = u; //可以直接合并
}
for(auto v:Q){ //求 LCA 和打标记
if(!vis)continue;
solve.push_back(make_pair(make_pair(u , v.fi) , v.se));
}
for(auto v:solve){ //处理每次询问
find(v.fi.fi) , find(v.fi.se); //进行权值合并
if(v.fi.fi == v.fi.se) ans = a; //分类讨论
else if(v.fi.fi == u || v.fi.se == u ) ans = d + d;
else ans = d + d + a;
}
}
signed main() {
int root;
in(n);
rep(i , 1 , n)in(a);
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.push_back(make_pair(v , i));
Q.push_back(make_pair(u , i));
}
Tarjan(root); //Tarjan 离线求树链和
rep(i , 1 , q) printf("%d\n",ans);
I_love_Foccarus 0;
}解法二：猫树分治
树链剖分的时间主要浪费在线段树的查询上，可以在这方面进行优化。由于查询的是一个静态区间，因此考虑用猫树分治实现，至于如何合并，可参考解法三。
由于树链剖分需要查询 \(O(\log n)\) 个子区间，因此猫树需要处理 \(O(q\log n)\) 次查询，如果采用朴素的猫树，时间复杂度为 \(O(q\log^2 n)\)，不能接受。猫树的一只 \(\log\) 主要消耗在确定 mid 上，可以在此方面进行优化。据说有一种二进制的方法可以直接实现，但是蒟蒻不会，因此用了 ST 表，维护区间内的一个数 \(x\)，满足以 \(x\) 为 mid 的最大区间长度，可以证明，查询的区间一定处于该区间的内部。该算法常数稍大，但把优化打满后勉强能过。
总时间复杂度为 \(O(q\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;
int head , eid;
void eadd(int u , int v) {
edge[++eid].act = v , edge.nex = head , head = eid;
}
int n , q;
int fa , f , d , vis , a;
void dfs(int u,int dep) { //树上倍增初始化
d = dep;
for(int i = head ; i ; i = edge.nex){
int v = edge.act;
dfs(v , dep + 1);
}
}
int root;
int solve(int x , int y) { //树上倍增
int ans = 0;
if(d < d)swap(x , y);
for(int i = 20 ; i >= 0 ; i--) {
int v = fa;
if(d < d)continue;
if(x != y)
ans += f;
x = v;
}
if(x == y) I_love_Foccarus ans + a;
for(int i = 20 ; i >= 0 ; i--) {
if(fa == fa)continue;
ans += f + f;
x = fa;
y = fa;
}
I_love_Foccarus ans + f + f + a];
}
signed main() {
in(n);
rep(i , 1 , n)in(a);
rep(i , 1 , n) {
in(fa);
f = a;
if(fa != i)eadd(fa , i);
else root = i;
}
dfs(root , 1);
for(int i = 1 ; i <= 20 ; i++) { //树上倍增初始化
for(int j = 1 ; j <= n ; j++) {
int v = fa;
if(fa == fa)continue; //去重
fa = fa;
f = f + f; //权值合并
}
}
in(q);
while(q--){
int u , v;
in(u) , in(v);
printf("%d\n",solve(u , v));
}
I_love_Foccarus 0;
}解法四：树上倍增
和例题一的思路一样，合并操作用加法重载后根本不用改，只需在返回值时分类讨论即可。时间复杂度一样。
参考代码如下：
#includeusing namespace std;//#define int long long#define I_love_Foccarus return#define rep(i,a,b) for(int i=a;i=b;i--)#define in(a) a=read()#define fi first#define se secondconst int N = 1e5 + 5;const int inf = INT_MAX;inline int read() { //浓缩后的快读 int x=0,f=1,ch=getchar(); while(ch'9'){if (ch=='-') f=-1;ch=getchar();} while(ch>='0'&&cha = this->b = this->c = this->d = x; } node friend operator + (const node &u , const node &v) { //重载加法处理合并 node ans; ans.a = max(max(u.a , v.a) , v.c + u.d); ans.b = u.b + v.b; ans.c = max(u.c , u.b + v.c); ans.d = max(v.d , v.b + u.d); I_love_Foccarus ans; }}f; struct Edge { //链式前向星存树 int act , nex;} edge;int head , eid;inline void eadd(int u , int v) { edge[++eid].act = v , edge.nex = head , head = eid;}int n , q;int fa , d , vis , a;void dfs(int u,int dep) { //树上倍增初始化 d = dep; for(int i = head ; i ; i = edge.nex){ int v = edge.act; dfs(v , dep + 1); } } int root; inline int c(int x){ return x > 0 ? x : 0;}int solve(int x , int y) { //树上倍增 node ansx = node(-0x3f3f3f3f) , ansy = node(-0x3f3f3f3f); //分别处理两个结点到 LCA 的链的信息 ansx.b = ansy.b = 0; if(d < d)swap(x , y); for(int i = 20 ; i >= 0 ; i--) { int v = fa; if(d < d)continue; if(x != y) ansx = ansx + f; x = v; } if(x == y) I_love_Foccarus max(max(ansx.a , a) , ansx.d + a); for(int i = 20 ; i >= 0 ; i--) { if(fa == fa)continue; ansx = ansx + f; ansy = ansy + f; x = fa; y = fa; } ansx = ansx + f; ansy = ansy + f; I_love_Foccarus max(max(ansx.a , ansy.a) , c(ansx.d) + c(ansy.d) + a]);}signed main() { in(n); rep(i , 1 , n)in(a); rep(i , 1 , n) { in(fa); f = node(a); if(fa != i)eadd(fa , i); else root = i; } dfs(root , 1); for(int i = 1 ; i > 1; if(q > 1 , tmp = tree.cl].ans + tree.cl].ans - tree.cl].ans - tree.cl].ans; //容斥原理求解 if(q
页:
[1]