全局平衡二叉树

可以较轻松的维护动态 $\text{dp}$ ，其他时候不建议使用。

其基础是静态的二叉搜索树，但并不是整个树结构都满足二叉，准确的说，每条重链使用一个二叉搜索树维护。

构建方式是对每条重链以轻子树大小和为权值按权分治找到左右儿子。

可以证明，一个点的深度为 $\Theta(\log n)$ 级别。

$\text{Proof}$ ：

考虑把重链拍成序列，每个点代表的轻子树大小和一定不会超过该点后的后缀和（因为是轻儿子），所以假设左边仍然比右边小太多，没有达到 $1:2$ 的比例，那左边从右边薅一个点最多薅走右边总大小的一半，也就是将中部的一个点扔到左边之后比例不会超过 $2:1$ ，也就是说每跳一次父亲 $\text{size}$ 至少翻 $1.5$ 倍，复杂度为 $\Theta(\log_{1.5}n)$ 。

模板：

// Problem: P4751 【模板】"动态DP"&动态树分治（加强版）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4751
// Memory Limit: 250 MB
// Time Limit: 3500 ms

#include<bits/stdc++.h>
#define l(x) ls[x]
#define r(x) rs[x]
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
using namespace std;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<21];
int read() {
    int s=0,w=0;char ch=gc();
    while(ch<'0'||ch>'9') w|=(ch=='-'),ch=gc();
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=gc();
    return w?-s:s;
} const int N=1e6+5;
basic_string<int> G[N];
int siz[N],dfn[N],dfx[N],a[N],son[N],Fa[N],l(N),r(N),n,m,la,fa[N];
struct MAT {
    int a[2][2];
    MAT() {a[0][0]=a[0][1]=a[1][0]=a[1][1]=-1e9;}
    int *operator[](int x) {return a[x];}
    void E() {
        a[0][0]=a[1][1]=0;
        a[0][1]=a[1][0]=-1e9;
    }
    MAT operator*(MAT &b) {MAT c;
        F(i,0,1) F(j,0,1) F(k,0,1) c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
        return c;
    }
} F[N],Z[N];
void Add(int x,int y) {G[x]+=y;G[y]+=x;}
void upd(int x,int v) {
    Z[Fa[x]][0][0]+=v*max(F[x][0][0],F[x][0][1]);
    Z[Fa[x]][1][0]+=v*max(F[x][0][0],F[x][0][1]);
    Z[Fa[x]][0][1]+=v*F[x][0][0];
}
void d(int x) {siz[x]=1;
    for(int v:G[x]) if(v^fa[x]) {
        fa[v]=x,d(v),siz[x]+=siz[v],siz[v]>siz[son[x]]&&(son[x]=v);
    }
}
void d2(int x) {dfn[x]=++*dfn;dfx[dfn[x]]=x;
    if(son[x]) d2(son[x]);
    for(int v:G[x]) if(v^fa[x]&&v^son[x]) d2(v);
}
#define up(d) (F[d]=F[r(d)]*Z[d]*F[l(d)])
int cbd(int L,int R) {if(L>R) return 0;
    int all=0,m=L-1,sz=0;
    F(i,L,R) all+=siz[dfx[i]]-siz[son[dfx[i]]];
    while(sz*2<all) ++m,sz+=siz[dfx[m]]-siz[son[dfx[m]]];
    int x=dfx[m];Fa[l(x)=cbd(L,m-1)]=x;Fa[r(x)=cbd(m+1,R)]=x;
    up(x);return x;
}
int bd(int x) {int s1=x,s2=x,s3;
    for(;x;x=son[s2=x]) for(int v:G[x]) if(v^son[x]&&v^fa[x]) Fa[s3=bd(v)]=x,upd(s3,1);
    return cbd(dfn[s1],dfn[s2]);
}
void mo(int x,int v) {Z[x][0][1]+=v-a[x];a[x]=v;
    for(;x;x=Fa[x]) if(x^l(Fa[x])&&x^r(Fa[x])) upd(x,-1),up(x),upd(x,1);
    else up(x);
}
int main() {F[0].E();
    n=read();m=read();
    F(i,1,n) a[i]=read(),Z[i][0][1]=a[i],Z[i][0][0]=Z[i][1][0]=0;
    F(i,2,n) Add(read(),read());d(1);d2(1);int rt=bd(1);
    F(i,1,m) {
        int x=read()^la,y=read();mo(x,y);
        printf("%d\n",la=max(F[rt][0][0],F[rt][0][1]));
    }
    return 0;
}

横着的向量要写成 F[d]=F[r(d)]*Z[d]*F[l(d)]，竖着的写成 F[d]=F[l(d)]*Z[d]*F[r(d)]。