先挂一张jijidawang的图
所以学这玩意就是被TopTree薄纱的
有人把这玩意叫静态的LCT，然而可能只需要一些LCT的知识，并不需要会LCT。起码我不会
注意这叫GBT，不叫GPT，能聊天的那个是CatGPT，不是CatGBT。
前置知识：树链剖分
用途
\(O(\log n)\)处理树上链修改、链查询、子树修改、子树查询、求LCA等，还可以用于\(O(\log n)\)处理动态dp。
主要是常数比LCT小，因为是静态的，没有splay等操作。
性质与构造
就是将一条重链拍成一个二叉树，然后将这几条重链连起来，构成一个高度为\(\log n\)的树，且二叉树上左儿子的深度比根节点小，右儿子比根节点深度大。
给张图，大概就是这样的。
然后给它拍成二叉树大概就是这个样子的
其中虚线边表示二叉树连二叉树，实线边表示二叉树所维护的重链。
那么如何建树可以使得树高为\(\log n\)的且满足以上性质呢?
先和普通重剖一样，求出一个点的重儿子，然后从根开始，把根所在的重链提出来，对重链上的点的轻儿子递归建树。
而这条重链上的点，先按照深度递增排序，然后求出每个点轻儿子的子树大小+1，按照这个，求出这条重链的加权中点，把它作为二叉树的根，然后递归建树。
建树应该挺好理解的。
点此查看代码
void dfs1(rint x){
siz[x] = 1;
for(int y:e[x]){
dfs1(y);siz[x] += siz[y];
if(!son[x] || siz[son[x]] < siz[y]) son[x] = y;
}
}
int buildc(rint ql,rint qr){
rint l = ql,r = qr,pos = 0,len = (sc[qr] - sc[ql]);
while(l <= r){
rint mid = (l + r) >> 1;
if(((sc[mid]-sc[ql])<<1) <= len) pos = mid,l = mid + 1;
else r = mid - 1;
}//二分求加权中点，也可以O(n)扫描
rint x = c[pos];ss[x] = qr-ql;//ss[x]表示以这个点为根的二叉树维护的重链长度
if(ql < pos) fa[lc[x] = buildc(ql,pos)] = x;
if(pos + 1 < qr) fa[rc[x] = buildc(pos+1,qr)] = x;
return x;
}
int build(rint x){
rint y = x;
do for(int v:e[y]) if(v ^ son[y]) fa[build(v)] = y; while(y = son[y]);
y = 0;
do c[y++] = x,sc[y] = sc[y-1] + siz[x] - siz[son[x]];while(x = son[x]);
return buildc(0,y);
}
证明为啥树高是\(\log n\)的。
从一个节点跳到根，最多跳\(O(\log n)\)条轻边。因为建树时求的是算轻儿子加权中点，所以跳一次重边轻儿子的节点数翻倍，所以最多跳\(O(\log n)\)条重边，复杂度\(O(\log n)\)。
应用
模板题：[LNOI2014] LCA
差分处理，挂扫描线，\(dep[LCA(x,y)]\)等价于将\(x\)到根的节点点权加一，然后计算\(y\)到根节点的点权和。
建出GBT来，然后用标记永久化写可以轻松成为最优解。
当然也可以将要跳的链处理出来，然后pushdown+pushup，但常数大大的。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
FILE *InFile = Infile(in),*OutFile = Outfile(out);
// FILE *ErrFile = Errfile(err);
#else
FILE *InFile = stdin,*OutFile = stdout;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define eb emplace_back
const int N = 5e4 + 10,mod = 201314;
vector<int> e[N],q1[N],q2[N];
int siz[N],son[N],fa[N],n,m,c[N],sc[N],lc[N],rc[N],q[N],ans[N],ss[N];
void dfs1(int x){
siz[x] = 1;
for(int y:e[x]){
dfs1(y),siz[x] += siz[y];
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
int buildc(int ql,int qr){
// cerr<<ql<<' '<<qr<<'\n';
int l = ql,r = qr,pos = 0,len = sc[qr]-sc[ql];
while(l <= r){
int mid = (l + r) >> 1;
if(2*(sc[mid]-sc[ql]) <= len) pos = mid,l = mid + 1;
else r = mid - 1;
}
int x = c[pos];ss[x] = qr-ql;
if(ql < pos) fa[lc[x] = buildc(ql,pos)] = x;
if(pos + 1 < qr) fa[rc[x] = buildc(pos+1,qr)] = x;
return x;
}
int build(int x){
int y = x;
do for(int v:e[y]) if(v != son[y])fa[build(v)] = y; while(y = son[y]);
do c[y++] = x,sc[y] = sc[y-1] + siz[x] - siz[son[x]]; while(x = son[x]);
return buildc(0,y);
}
int tag[N],sum[N];
inline void upd(int x){
bool flag = true;int val = 0;
while(x){
sum[x] += val;
if(flag){
tag[x]++;
if(rc[x]) tag[rc[x]]--;
val += ss[lc[x]] + 1;
sum[x] -= ss[rc[x]];
}
flag = (x != lc[fa[x]]);
if(flag && rc[fa[x]] != x) val = 0;
x = fa[x];
}
}
inline int qry(int x){
int res = 0,val = 0;
bool flag = true;
while(x){
if(flag){
res += sum[x] - sum[rc[x]];
res -= ss[rc[x]]*tag[rc[x]];
val += ss[lc[x]] + 1;
}
res += val*tag[x];
flag = (x != lc[fa[x]]);
if(flag && x != rc[fa[x]]) val = 0;
x = fa[x];
}
return res;
}
inline void solve(){
cin>>n>>m;
rep(i,2,n,1){int f;cin>>f;f++;e[f].eb(i);}
dfs1(1);build(1);
rep(i,1,m,1){
int l,r;cin>>l>>r>>q[i];r++,q[i]++;
q2[r].eb(i);if(l) q1[l].eb(i);
}
rep(i,1,n,1){
upd(i);
for(auto j:q1[i]) ans[j] -= qry(q[j]);
for(auto j:q2[i]) ans[j] += qry(q[j]);
}
rep(i,1,m,1) cout<<ans[i]%mod<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
处理子树和还要维护子树和和打子树标记，然后维护动态dp什么的就直接用pushup？(雾)
没怎么学动态dp啊。
标签：log,int,siz,笔记,二叉树,using,全局,重链 From： https://www.cnblogs.com/hzoi-Cu/p/18494445