[TOC]
树上倍增
适用场景：寻找一棵树的k代祖先，可以类似二次幂的思路。初始化每一个节点的 1，2，4，log(h) 代祖先，这样的话，初始化复杂度为 O(n log h) 。之后寻找k代祖先的单次查找复杂度为 O(log k)，适用于多次查询的场景。
Template（以 leetcode 2836 为例）
class Solution {
public:
long long getMaxFunctionValue(vector<int>& receiver, long long k) {
n = len(reveiver)
// 定义最大查找长度，1<<0为父亲，1<<(k.bit_length()-1)
m = k.bit_length()-1
pa = [[(p,p)]+[None]*m for p in receiver]
for i in range(m):
for x in range(n):
// 寻找节点 x 的 1<<i 代祖先p和cost
p,s = pa[x][i]
// 寻找节点 p 的 1<<i 代祖先pp和cost
pp,ss = pa[p][i]
// 那么节点 x 的 1<<(i+1) 代祖先就是pp，cost就是代之间的加和
pa[x][i+1] = (pp,s+ss)
res = 0
for i in range(n):
// 遍历每一个节点
sum = 0
x = i
for j in range(m+1):
//遍历k的每一个二级制位
if (k>>j)&1:
// 若 1<<j 代祖先存在，则将当前节点迭代至 1<<j 代祖先
x,s = ps[x][j]
// 累计 cost 加和
sum += s
res = max(res,sum)
return res
}
};
