Top Trees 领先®

Top Trees 领先®

全局平衡二叉树

你要在 O(nlog⁡n)\mathcal{O}(n\log n) 的时间内解决：

  1. 给 1∼x1\sim x 路径上的点权 +1+1。
  2. 求 1∼x1\sim x 路径上的点权和。

最经典的解法当然是 O(log⁡2n)\mathcal{O}(\log^2n) 的树链剖分，然而复杂度过劣，于是就有了全局平衡二叉树。

想一想树剖的做法有没有什么优化的空间：

  • 给每一个重链单独开一个线段树，这样常熟更小。
  • 对于每一个线段树，我们希望比较“重”的节点深度更小一点，因为在到达这个节点之前我们付出了更大的代价。
  • 那么，我们可以在建立线段树的时候，不再从区间中点分治，而是带权分治——权值为 szx−szsonxsz_x-sz_{son_x}，即其子树的“重量”。
  • 那么我们从某一个节点往上跳，若经过轻边，则子树大小必然翻倍。若经过重边，由于带权分治，子树大小依然翻倍。
  • 于是树高 O(log⁡n)\mathcal{O}(\log n)。
  • 那么我们就完成了这一优化。

经典的例题是 [LNOI2014] LCA。这里放一下其维护链加链和的代码：

::::success[全局平衡二叉树]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
void dfs(int x,int fa){
    sz[x]=1;
    for(int i=0;i<v[x].size();i++){
        int u=v[x][i];
        if(u==fa)continue;
        dfs(u,x);
        sz[x]+=sz[u];
        if(sz[u]>sz[son[x]])son[x]=u;
    }
}
int cbuild(int ql,int qr){
    int l=ql,r=qr;
    while(r-l>1){
        int mid=(l+r)>>1;
        if(2*(bs[mid]-bs[ql])<=(bs[qr]-bs[ql]))l=mid;
        else r=mid;
    }
    int x=b[l];
    ss[x]=qr-ql;
    if(ql<l){
        ls[x]=cbuild(ql,l);
        f[ls[x]]=x;
    }
    if(l+1<qr){
        rs[x]=cbuild(l+1,qr);
        f[rs[x]]=x;
    }
    return x;
}
int build(int x,int fa){
    int y=x,Fa=fa;
    do{
        for(int u:v[y]){
            if(u!=Fa&&u!=son[y])f[build(u,y)]=y;
        }
    }while(Fa=y,y=son[y]);
    y=0;
    do{
        b[y++]=x;
        bs[y]=bs[y-1]+sz[x]-sz[son[x]];
    }while(x=son[x]);
    return cbuild(0,y);
}
void change(int x){
    int t=1,z=0;
    while(x){
        s[x]+=z;s[x]%=P;
        if(t){
            a[x]++;a[x]%=P;
            if(rs[x])a[rs[x]]=(a[rs[x]]-1+P)%P;
            z+=1+ss[ls[x]];
            s[x]-=ss[rs[x]];s[x]=(s[x]+P)%P;
        }
        t=(x!=ls[f[x]]);
        if(t&&x!=rs[f[x]])z=0;
        x=f[x];
    }
}
int getans(int x){
    int t=1,z=0,res=0;
    while(x){   
        if(t){
            res+=(s[x]-s[rs[x]]+P)%P;res%=P;
            res-=1ll*ss[rs[x]]*a[rs[x]]%P;res=(res+P)%P;
            z+=1+ss[ls[x]];
        }
        res+=1ll*z*a[x]%P;res%=P;
        t=(x!=ls[f[x]]);
        if(t&&x!=rs[f[x]])z=0;
        x=f[x];
    }
    return res;
}

::::

不得不承认这个数据结构精巧而无用。主要是“从下往上”这一操作太反人类了。而且由于其对于每一个重链单开一个线段树（或者说是平衡二叉树），其天然不支持子树操作（而且就连链的操作也十分复杂，甚至由于是平衡二叉树，必须特判儿子的存在性）。

因此这个东西最大的用处就是 DDP，然而这个东西也要被 Top Tree 替代了。（不对好像静态 Top Tree 是基于他的）

静态 Top Tree

Top Tree 最基本的理论：树簇理论。

先放一张陈年老图：

其中，compress⁡\operatorname{compress} 操作，可以令 (a,b)(b,c)→(a,c)(a,b)(b,c)\to (a,c)，即，对于只有一个子节点的点，把这个点“压缩”掉。

然后，rake⁡\operatorname{rake} 操作，可以令 (a,b)(a,c)→(a,c)(a,b)(a,c)\to (a,c)，即，对于一个叶子节点，可以把他“并”到另一个节点上。

可以证明，compress⁡\operatorname{compress} 和 rake⁡\operatorname{rake} 可以将树收缩为一个仅有一条边的连通块。

同时，任意一个时刻，任意一个点，一定对应这原图一个连通块（这个连通块是由任意次 compress⁡\operatorname{compress} 和 rake⁡\operatorname{rake} 收缩成这一点的）。这样的一个被收缩的连通块称为“树簇”。

一个树簇必然有一个深度最小的“根”，以及一个最下面的“叶子”构成，这两个点称为树簇的上下界点；换句话说，如果只 rake⁡\operatorname{rake}，那么得到的树簇将会是一条链，这个链的上下界点就是树簇的上下界点。

显然的，compress⁡\operatorname{compress} 和 rake⁡\operatorname{rake} 操作可以将信息合并，例如树簇大小或者两界点的距离，或者其他的什么可以合并的信息（例如 DP 转移）。

::::info[例子]

例如我们可以维护树簇的上下界点的距离 lenlen 以及树簇大小 szsz：

  • compress⁡(x,y)\operatorname{compress}(x,y)：
    • len=lenx+lenylen=len_x+len_y；
    • sz=szx+szysz=sz_x+sz_y。
  • rake⁡(x,y)\operatorname{rake}(x,y)：
    • len=lenylen=len_y；
    • sz=szx+szysz=sz_x+sz_y。

::::

以上就是 Top Tree 的树簇理论的最基本的东西了。

由于 compress,rake⁡\operatorname{compress,rake} 都有公共点，我们不妨把这个过程用二叉树表示出来，例如：

那么当我修改某一条边的信息时，只需要一路 compress⁡\operatorname{compress} 或者 rake⁡\operatorname{rake} 上去就行。那么只要我能构造出一个树高有保证的树，我就可以轻松完成动态修改。

一个基本的想法是树链剖分：将每一个重链上的点进行 compress⁡\operatorname{compress} 合并，对于每一个节点的轻儿子，使用 rake⁡\operatorname{rake} 合并到重儿子上。容易证明树高 O(log⁡2n)\mathcal{O}(\log^2n)。

然而这还不够好。我们可以使用上面的全局平衡二叉树就行优化，这样树高就有 O(log⁡n)\mathcal{O}(\log n) 了。

维护动态 DP

【模板】动态 DP（加强版）。

求树的最大独立集大小，点带权，每次单点修改求答案。

n,m≤106n,m\le 10^6。

令 fx,0/1,0/1f_{x,0/1,0/1} 表示树簇 xx，上/下节点没被删/删了的最大独立集大小。

则：

  • u=compress⁡(x,y)u=\operatorname{compress}(x,y)：
    • fu,a,b←fx,a,c+fy,c,bf_{u,a,b}\leftarrow f_{x,a,c}+f_{y,c,b}。
  • u=rake⁡(x,y)u=\operatorname{rake}(x,y)：
    • fu,a,b←fx,a,c+fy,a,bf_{u,a,b}\leftarrow f_{x,a,c}+f_{y,a,b}。

（上述状态设计和转移是因为要保证树簇的拼接点状态相同。）

::::success[代码]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
const int N=2000100,inf=1e9;
using node=array<array<int,2>,2>;
using pii=pair<int,int>;
using sti=vector<pii>::iterator;
int n,m,tot,ls[N],rs[N],f[N],F[N];
int sz[N],son[N],ty[N];
node a[N];
vector<int>v[N];
node rake(node &a,node &b){
    node c;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)
        c[i][j]=max(a[i][0],a[i][1])+b[i][j];
    return c;
}
node compress(node &a,node &b){
    node c;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)
        c[i][j]=max(a[i][0]+b[0][j],a[i][1]+b[1][j]);
    return c;
}
void up(int p){
    if(ty[p])a[p]=compress(a[ls[p]],a[rs[p]]);
    else a[p]=rake(a[ls[p]],a[rs[p]]);
}
int add(int x,int y,int t){
    ls[++tot]=x,rs[tot]=y;
    f[x]=f[y]=tot;ty[tot]=t;
    up(tot);
    return tot;
}
void dfs(int x,int fa){
    sz[x]=1;F[x]=fa;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
        sz[x]+=sz[u];
        if(sz[u]>sz[son[x]])son[x]=u;
    }
}
int dc(sti l,sti r,int t){
    if(l+1==r)return l->first;
    int sum=0;
    for(sti it=l;it!=r;it++)sum+=it->second;
    sti mid=l;
    while(mid+1!=r&&sum>0)sum-=mid->second<<1,mid++;
    return add(dc(l,mid,t),dc(mid,r,t),t);
}
int dfs2(int x){
    int y=x;
    vector<pii>tmp{{x,1}};
    while(son[y]){
        vector<pii>ch;
        for(int u:v[y])
            if(u!=F[y]&&u!=son[y])
                ch.emplace_back(dfs2(u),sz[u]);
        ch.emplace_back(son[y],1);
        tmp.emplace_back(dc(ch.begin(),ch.end(),0),sz[y]-sz[son[y]]);
        y=son[y];
    }
    return dc(tmp.begin(),tmp.end(),1);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i][0][1]),a[i][1][1]=-inf;
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    tot=n;
    int rt=dfs2(1),lst=0;
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        x^=lst,a[x][0][1]=y;
        while(x=f[x])up(x);
        printf("%d\n",lst=max(a[rt][0][1],a[rt][0][0]));
    }
    return 0;
}

::::

维护子树答案/链答案

洪水。

小 A 走到一个山脚下，准备给自己造一个小屋。这时候，小 A 的朋友（op，又叫管理员）打开了创造模式，然后飞到山顶放了格水。于是小 A 面前出现了一个瀑布。作为平民的小 A 只好老实巴交地爬山堵水。那么问题来了：我们把这个瀑布看成是一个 nn 个节点的树，其中树根为 11， 每个节点有权值（爬上去的代价）。小 A 要选择一些节点，以其权值和作为代价将这些点删除（堵上），使得根节点与所有叶子结点不连通。问最小代价。不过到这还没结束。小 A 的朋友觉得这样子太便宜小 A 了，于是他还会不断地修改地形，使得某个节点的权值发生变化。不过到这还没结束。小 A 觉得朋友做得太绝了，于是放弃了分离所有叶子节点的方案。取而代之的是，每次他只要在某个子树中（和子树之外的点完全无关）。于是他找到你。

令 fx,0/1,0/1f_{x,0/1,0/1} 表示树簇 xx，上/下节点没被删/删了的最小代价大小。

则：

  • u=compress⁡(x,y)u=\operatorname{compress}(x,y)：
    • fu,a,b←fx,a,c+fy,c,bf_{u,a,b}\leftarrow f_{x,a,c}+f_{y,c,b}。
  • u=rake⁡(x,y)u=\operatorname{rake}(x,y)：
    • fu,a,b←fx,a,c+fy,a,bf_{u,a,b}\leftarrow f_{x,a,c}+f_{y,a,b}。

这些都是简单的，主要是他求的是子树答案。

观察一下 Top Tree 树结构，容易发现，对于子树 xx，其内部的所有边权由其轻儿子构成的 rake⁡\operatorname{rake} 子树，以及其所在重链的后半部分构成的，因此可以用以下代码：

1
2
3
4
5
6
7
8
int t=son[x];
while(!ty[f[t]])t=f[t];
node ans=a[t];
while(ty[f[t]]){
    if(ls[f[t]]==t)
        ans=compress(ans,a[rs[f[t]]]);
    t=f[t];
}

PS: 注意维护的是边权，实际写的时候要加上 xx 自己的贡献。

::::success[代码]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=800100,inf=1e18;
using node=array<array<int,2>,2>;
using pii=pair<int,int>;
using sti=vector<pii>::iterator;
int n,m,tot,ls[N],rs[N],f[N],F[N];
int sz[N],son[N],ty[N];
node a[N];
vector<int>v[N];
node rake(node &a,node &b){
    node c;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)
        c[i][j]=min(a[i][0],a[i][1])+b[i][j];
    return c;
}
node compress(node &a,node &b){
    node c;
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)
        c[i][j]=min(a[i][0]+b[0][j],a[i][1]+b[1][j]);
    return c;
}
void up(int p){
    if(ty[p])a[p]=compress(a[ls[p]],a[rs[p]]);
    else a[p]=rake(a[ls[p]],a[rs[p]]);
}
int add(int x,int y,int t){
    ls[++tot]=x,rs[tot]=y;
    f[x]=f[y]=tot;ty[tot]=t;
    up(tot);
    return tot;
}
void dfs(int x,int fa){
    sz[x]=1;F[x]=fa;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
        sz[x]+=sz[u];
        if(sz[u]>sz[son[x]])son[x]=u;
    }
    if(!son[x])a[x][0][0]=inf;
}
int dc(sti l,sti r,int t){
    if(l+1==r)return l->first;
    int sum=0;
    for(sti it=l;it!=r;it++)sum+=it->second;
    sti mid=l;
    while(mid+1!=r&&sum>0)sum-=mid->second<<1,mid++;
    return add(dc(l,mid,t),dc(mid,r,t),t);
}
int dfs2(int x){
    int y=x;
    vector<pii>tmp{{x,1}};
    while(son[y]){
        vector<pii>ch;
        for(int u:v[y])
            if(u!=F[y]&&u!=son[y])
                ch.emplace_back(dfs2(u),sz[u]);
        ch.emplace_back(son[y],1);
        tmp.emplace_back(dc(ch.begin(),ch.end(),0),sz[y]-sz[son[y]]);
        y=son[y];
    }
    return dc(tmp.begin(),tmp.end(),1);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1,x;i<=n;i++){
        scanf("%lld",&x);
        a[i][0][1]=x;
    }
    for(int i=1,x,y;i<n;i++){
        scanf("%lld%lld",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    scanf("%lld",&m);
    dfs(1,0);
    tot=n;
    int rt=dfs2(1);
    while(m--){
        char opt;
        int x,y;
        scanf(" %c%lld",&opt,&x);
        if(opt=='C'){
            scanf("%lld",&y);
            a[x][0][1]+=y;
            while(x=f[x])up(x);
        }
        else{
            if(!son[x])printf("%lld\n",a[x][0][1]);
            else{
                int t=son[x];
                while(!ty[f[t]])t=f[t];
                node ans=a[t];
                while(ty[f[t]]){
                    if(ls[f[t]]==t)
                        ans=compress(ans,a[rs[f[t]]]);
                    t=f[t];
                }
                printf("%lld\n",
                    min({a[x][0][1],ans[0][1],ans[0][0]}));
            }
        }
    }
    return 0;
}

::::

链的话，和全局平衡二叉树是类似的。

应该还有其他好玩的应用，可惜我还没找出来。

维护的东西还可以是例如树的直径（维护两界点距离，树簇直径，两界点分别的树簇内最远距离）之类的东西，只需要维护好两界点状态就行。