自顶向下的 leaf 的 rake 的全局平衡二叉树
前置科技
（阅读本文不需要，但是看懂我写的标程需要看一下。）
rake
全局平衡二叉树不支持子树修改，这十分傻，怎么解决呢？
我会三度化
三度化后每个节点最多只有一个轻子树，可以暴力 push_down，push_up。 注意，三度化可能会让 lca 选到虚点，此时我们需要将这个虚点对应的实点手动加入路径，下文会介绍一个诡异的实现方式。
我会 top tree
我们可以直接对每个节点建个 rake tree，而在重链仍然使用全局平衡二叉树的结构，这样跟 top tree 的区别就是不用点集化了，因为它对重链是按点建的。
我会不管
考虑直接建 rake tree，然后把他视为一个对重链建的全局平衡二叉树，我们声称这就是对的。
具体来说，建 rake tree 就是为了三度化，此时 rake tree 就对应一条只包含虚点的重链。
leaf
leaf 的全局平衡二叉树想必大家都知道，leaf 的 rake tree 也是好实现的，于是我们就得到了一个 leaf 的这东西。
组合意义就是非叶子节点对应一条重边，叶子节点对应点，rake tree 的叶子对应轻边，非叶子对应它在原树上的父亲这个点，所以你维护边相关信息时会跟平衡树长得差不多，且你不用再写边集化了。
目前，似乎只有这个东西能同时干掉点集化和边集化。
自顶向下
传统的全局平衡二叉树是自下向顶的，导致链操作实现非常反人类。
有一个结论，就是重链上的一个区间，其对应的轻子树在 dfs 序也是一个区间，这个读者自证不难，不过要注意，dfs 序小的节点对应的轻子树 dfs 序反而更大，想要解决这个问题可以考虑翻转一下 dfs 序，不过翻转过后它对应的 dfs 序区间还是两个。
因此，我们就可以
如果我们发现查询的链就是这个节点对应的重链，就直接返回。
发现这条链在轻子树 + 当前节点中就算上这个点的贡献，向轻子树递归。
如果都完全在左右节点中的一个，直接递归，反之就从中间劈开，再递归。
搭配上 leaf，我们就可以只写 5 种情况，而不是 9 种。
注意，这个东西你无法保证 dfs 序小的一定在左边，大的一定在右边，因为其没有祖孙关系。
这个复杂度看起来有点错，但是实际上是对的。
考虑设
然后就可以列出
显然是一个老哥的，从而，我们就可以实现自顶向下，而且这个东西不需要求个 lca 再分开，也不需要对 lca 所在的重链做特判。
子树修改就等价于对点到对应重链底这条链本身和其轻子树做修改。
同时这个东西可以顺带求 lca，因为 lca 是路径上 dfs 序最小的点。
细节
这个东西做一些点相关的东西可能不能完全不管，就是push_up，push_down 必须得管一下。
如果在 rake tree 中记一下对应的实点，在 rake tree 中分治时如果发现链的两个端点分别在左边和右边且都为实点，就在中间加入对应的实点，这个显然不会算重，也不需要求 lca，且可以非常方便的实现严格的按顺序访问。
非常奇特的，我们可以将实点视作 rake tree 的非叶子节点对应的边，将轻边视作 rake tree 的非叶子节点对应的点，就会发现这个东西大一统了，虽然将点视为边，边视为点有点奇怪，但是这样似乎没有破坏原树的性质，因为两个点中间有边和两个边中间有点看起来是差不多的。
这个东西应该是不弱于 top tree 的。
例题：
一道绝世好题，std。
所有静态且在树上的 top tree 可以做的题。
本来 top tree 做太石现在可以做的题（如某乘凉州题，提交记录，虽然因为我的常数有点大没能夺得最优解，但强制在线已经赢麻了，且在格式化后跟树剖做法长度几乎相同）。
一些细节：
该代码轻子树和重链是分开维护的，想要子树信息需要合并，好处就是支持不满足可减性的链改，坏处就是你要维护一个不连通的簇的信息。
翻转 dfs 序后这个东西几乎就跟线段树一模一样。
这个东西维护树上邻域就跟 top tree 几乎一模一样，考虑上界点和下界点的邻域，合并。
这个东西常数有点大，但是在常规数据跑得过树剖，大约是树剖的两三倍快，卡些常或者数据比较强可能差的多一点。
下述代码采用了一个十分神奇的建树方式，就是将重链对应的区间和轻子树对应的区间直接传进去，如果重链上只有一个点就递归建轻子树，反之就正常分治。
采用了完全无到儿子的指针的写法，跟前置科技说的 dfs 序线段树差不多。
采用了很多前置科技提到的写法，可能需要学习一下。
这里有一个非常 modern c++ 的模板树链剖分的代码，不长，也就 170 行。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int sz[N],ndf[N],dfn[N],dfr[N],ed[N],son[N],fw[N];
int es[N],ef[N],n,q,w,sd[N],mod,a[N];
vector<int> e[N],g[N];
int M(const int& x){
return x - ((-(x >= mod)) & mod);
}
struct node{
int s,ss,ad,as,l,mid,r,sl,sr;
int que(int l,int r){
return sd[r] - sd[l - 1];
}
#define lc (*(this + 1))
#define rc (*(this + (lc.qsz() << 1)))
#define mc (*(this + 1))
// 中儿子
int qsz(){
return (sl == 0)?r - l + 1:r - l + 1 + sr - sl + 1;
}
void push_up(){
if (l == r){
ss = M(mc.s + mc.ss);
return;
}
s = M(lc.s + rc.s);
ss = M(lc.ss + rc.ss);
}
void tag(int x,int y){
ss = (ss + 1ll * que(sl,sr) * y) % mod;
s = (s + 1ll * que(l,r) * x) % mod;
as = M(as + y),ad = M(ad + x);
}
void push_down(){
if (l == r){
return mc.tag(as,as),ad = as = 0,void();
}
lc.tag(ad,as),rc.tag(ad,as);
ad = as = 0;
}
bool in(int x){
return ((l <= x) && (r >= x)) || ((sl <= x) && (sr >= x));
}
void upd(int u,int v,const auto& Do){
(u > v) && (swap(u,v),1);
if ((l == u) && (r == v)){
return Do(*this);
}
push_down();
if (l == r){
return (l == u) && (Do(*this),1),mc.upd(mc.in(u)?u:mc.l,v,Do),push_up();
}
if (lc.in(u) && lc.in(v)){
lc.upd(u,v,Do);
}
else if (rc.in(u) && rc.in(v)){
rc.upd(u,v,Do);
}
else if (lc.in(u) && rc.in(v)){
lc.upd(u,mid,Do),rc.upd(mid + 1,v,Do);
}
else if (lc.in(v) && rc.in(u)){
lc.upd(v,mid,Do),rc.upd(mid + 1,u,Do);
}
push_up();
}
int qsz(int l,int r){
return sz[ndf[l]] - sz[son[ndf[r]]];
}
void build(int _l,int _r,int _sl,int _sr){
l = _l,r = _r,sl = _sl,sr = _sr;
if (l == r){
s = a[ndf[l]];
if (sl <= sr){
return mc.build(sl,ed[sl],ed[sl] + 1,sr),push_up();
}
return;
}
int ls = l,rs = r;
while (ls <= rs){
int mid = (ls + rs) >> 1;
(qsz(l,mid) * 2>= qsz(l,r))?rs = mid - 1:ls = mid + 1;
}
mid = max(l,min(ls,r - 1));
lc.build(l,mid,sl,dfr[mid]);
rc.build(mid + 1,r,dfr[mid] + 1,sr);
push_up();
}
}t[N << 2];
int gm,tot,cnt,own[N];
void sdh(int x,int fa){
vector<int > tmp;
for (auto &v : g[x]){
if (v ^ fa){
sdh(v,x);
tmp.push_back(v);
}
}
while (tmp.size() > 2){
++cnt;
auto v1 = tmp.back();
tmp.pop_back();
auto v2 = tmp.back();
tmp.pop_back();
e[cnt].push_back(v1);
e[cnt].push_back(v2);
own[cnt] = x;
tmp.push_back(cnt);
}
e[x] = tmp;
}
void dfs1(int x){
sz[x] = 1;
for (auto &v : e[x]){
dfs1(v);
sz[x] += sz[v];
(sz[v] > sz[son[x]]) && (son[x] = v);
}
}
void dfs2(int x){
for (int i = x;i;i = son[i]){
ndf[dfn[i] = ++tot] = i;
sd[tot] = sd[tot - 1] + (i <= n);
}
int ned = tot;
for (int i = x;i;i = son[i]){
for (auto &v : e[i]){
if (v ^ son[i]){
dfs2(v);
}
}
dfr[dfn[i]] = tot;
ed[dfn[i]] = ned;
}
}
int Ed(int x){
return ndf[ed[dfn[x]]];
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
int rt;
cin >> n >> q >> rt >> mod;
for (int i = 1;i <= n;i++){
cin >> a[i];
}
for (int i = 1,u,v,w;i < n;i++){
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cnt = n,sdh(rt,0);
dfs1(rt),dfs2(rt);
t[0].build(1,ed[1],ed[1] + 1,cnt);
for (int i = 1,op,x,y,z;i <= q;i++){
auto to_do = [&](int u,int v,const auto& Do){
u = dfn[u],v = dfn[v];
(u > v) && (swap(u,v),1);
int lca = 1e9;
t[0].upd(u,v,[&](node &a){Do(a),lca = min(lca,a.l);});
(own[ndf[lca]]) && (lca = dfn[own[ndf[lca]]],t[0].upd(lca,lca,Do),1);
};
cin >> op >> x;
(op == 1) && (cin >> y >> z,to_do(x,y,[&](node &a){a.tag(z,0);}),1);
(op == 2) && (cin >> y,z = 0,to_do(x,y,[&](node &a){z = (z + a.s) % mod;}),cout << z << "\n",1);
(op == 3) && (cin >> z,to_do(x,Ed(x),[&](node & a){a.tag(z,z);}),1);
(op == 4) && (z = 0,to_do(x,Ed(x),[&](node &a){z = (z + a.s + a.ss) % mod;}),cout << z << "\n",1);
}
}这里有一个 p6666 的不完全管的代码