简介

树链剖分是一种维护树上路径信息的算法，它将一棵树剖分成一些不相交的链，保证每个点在且仅在一条链上，并通过线段树、树状数组等数据结构维护每一条链上的信息

几个概念：
重儿子：父亲节点的所有儿子中子树结点数目最多的结点
轻儿子：父亲节点中除了重儿子以外的儿子
重边：父亲结点和重儿子连成的边
轻边：父亲节点和轻儿子连成的边
重链：由多条重边连接而成的路径
轻链：由多条轻边连接而成的路径

1

树剖一般用来解决以下问题：
修改点 $x$ 到点 $y$ 路径上各点的值
查询点 $x$ 到点 $y$ 路径上各点的值
修改点 $x$ 子树上各点的值
查询点 $x$ 子树上各点的值

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Edge
{
    int u,v,next;
}E[maxn<<1];
int Ecnt;

struct Node
{
    int head,top;    //top表示每条链上深度最小的点
    int fa,maxson;    //maxson表示该节点的最大子树
    int size,dfn,dep;    //size表示以这个节点为根的树的大小,dfn为dfs序,dep表示这个节点的深度
    bool vis;
}N[maxn];

剖分

1
2
3
4
5
6
void split(int u)
{
    N[u].dep=1;
    dfs1(u);
    dfs2(u);
}

剖分的过程由两次 $dfs$ 组成，第一次 $dfs$ 求出每个节点的 $size$ 和 $maxson$ ，第二次 $dfs$ 求出每个节点所在的链

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
void dfs1(int u)
{
    N[u].vis=true;
    N[u].size=1;
    for(int i=N[u].head;i;i=E[i].next)
    {
        int v=E[i].v;
        if(N[v].vis) continue;
        N[v].fa=u;
        N[v].dep=N[u].dep+1;
        dfs1(v);
        N[u].size+=N[v].size;
        if(!N[u].maxson || N[v].size>N[N[u].maxson].size) N[u].maxson=v;
    }
}

void dfs2(int u)
{
    static int ts=0;
    N[u].dfn=++ts;
    pdfn[ts]=u;

    if(!N[u].fa || u!=N[N[u].fa].maxson) N[u].top=u;
    else N[u].top=N[N[u].fa].top;

    if(N[u].maxson) dfs2(N[u].maxson);    //优先处理最大子树
    for(int i=N[u].head;i;i=E[i].next)
    {
        int v=E[i].v;
        if(N[v].fa==u && v!=N[u].maxson) dfs2(v);
    }
}

对于每个节点，如果它是根（没有父节点）或它不是父节点的最大子树（ $maxson$ ），则创建一条以该节点为链顶节点的链，否则该节点与其父节点在同一条链上
为了维护树上路径信息，我们记录每个点的 $dfs$ 序，为了使同一条链上的点在 $dfs$ 序中是相邻的，我们在 $dfs$ 时优先递归处理最大子树

线段树

建树

我们使用线段树维护每一条链的信息，以 $dfs$ 序建树，保证每条链上的节点在线段树中是连续的

1
2
Tree.Build(n);
void Build(int n){tree.build(1,1,n);}

查询路径

查询两个点 $u$ 与 $v$ 之间的点权和（或点权极值）的方法：
1.如果 $u$ 与 $v$ 不在同一条链上，不妨设 $u$ 所在链链顶节点深度较大，在线段树上查询 $u$ 所在链链顶节点 $N[u].top$ 到 $u$ 的路径，并将 $u$ 跳到其所在链链顶节点的父亲节点，即 $u=N[N[u].top].fa$
2.如果 $u$ 与 $v$ 在同一条链上，则直接在线段树中查询
注意查询时一定要以 $dfs$ 序作为区间端点查询

1
2
3
4
5
6
7
8
9
10
11
12
13
ll Querysum(int u,int v)
{
    ll ans=0;
    while(N[u].top!=N[v].top)
    {
        if(N[N[u].top].dep<N[N[v].top].dep) swap(u,v);
        ans+=tree.querysum(1,N[N[u].top].dfn,N[u].dfn);
        u=N[N[u].top].fa;
    }
    if(N[u].dep>N[v].dep) swap(u,v);
    ans+=tree.querysum(1,N[u].dfn,N[v].dfn);
    return ans;
}

题目

题目链接

「洛谷」P3384

题目大意

给一棵树，写一个程序，满足以下功能：
1.将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$
2.求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和
3.将以 $x$ 为根节点的子树内所有节点值都加上 $z$
4.求以 $x$ 为根节点的子树内所有节点值之和

完整代码

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
#define ll long long
#define ls rt<<1
#define rs rt<<1|1

int a[maxn],pdfn[maxn];

struct Link
{
    struct Edge
    {
        int u,v,next;
    }E[maxn<<1];
    int Ecnt;

    struct Node
    {
        int head,top;
        int fa,maxson;
        int size,dfn,dep;
        bool vis;
    }N[maxn];

    void add(int u,int v)
    {
        E[++Ecnt]=(Edge){u,v,N[u].head};N[u].head=Ecnt;
        E[++Ecnt]=(Edge){v,u,N[v].head};N[v].head=Ecnt;
    }

    void dfs1(int u)
    {
        N[u].vis=true;
        N[u].size=1;
        for(int i=N[u].head;i;i=E[i].next)
        {
            int v=E[i].v;
            if(N[v].vis) continue;
            N[v].fa=u;
            N[v].dep=N[u].dep+1;
            dfs1(v);
            N[u].size+=N[v].size;
            if(!N[u].maxson || N[v].size>N[N[u].maxson].size) N[u].maxson=v;
        }
    }

    void dfs2(int u)
    {
        static int ts=0;
        N[u].dfn=++ts;
        pdfn[ts]=u;

        if(!N[u].fa || u!=N[N[u].fa].maxson) N[u].top=u;
        else N[u].top=N[N[u].fa].top;

        if(N[u].maxson) dfs2(N[u].maxson);
        for(int i=N[u].head;i;i=E[i].next)
        {
            int v=E[i].v;
            if(N[v].fa==u && v!=N[u].maxson) dfs2(v);
        }
    }

    void split(int u)
    {
        N[u].dep=1;
        dfs1(u);
        dfs2(u);
    }

    struct SegT
    {
        struct node
        {
            int l,r;
            int len;
            ll sum,lazy;
        }t[maxn<<2];

        void pushup(int rt){t[rt].sum=t[ls].sum+t[rs].sum;}

        void pushdown(int rt)
        {
            if(!t[rt].lazy) return;
            t[ls].sum+=t[ls].len*t[rt].lazy;t[ls].lazy+=t[rt].lazy;
            t[rs].sum+=t[rs].len*t[rt].lazy;t[rs].lazy+=t[rt].lazy;
            t[rt].lazy=0;
        }

        void build(int rt,int l,int r)
        {
            t[rt].len=r-l+1;
            t[rt].l=l;t[rt].r=r;
            t[rt].sum=t[rt].lazy=0;
            if(l==r)
            {
                t[rt].sum=a[pdfn[l]];
                return;
            }
            int mid=(l+r)>>1;
            build(ls,l,mid);
            build(rs,mid+1,r);
            pushup(rt);
        }

        void add(int rt,int l,int r,ll val)
        {
            if(t[rt].l==l && t[rt].r==r)
            {
                t[rt].sum+=val*t[rt].len;
                t[rt].lazy+=val;
                return;
            }
            pushdown(rt);
            int mid=(t[rt].l+t[rt].r)>>1;
            if(r<=mid) add(ls,l,r,val);
            else if(l>=mid+1) add(rs,l,r,val);
            else add(ls,l,mid,val),add(rs,mid+1,r,val);
            pushup(rt);
        }

        ll querysum(int rt,int l,int r)
        {
            if(t[rt].l==l && t[rt].r==r) return t[rt].sum;
            pushdown(rt);
            int mid=(t[rt].l+t[rt].r)>>1;
            if(r<=mid) return querysum(ls,l,r);
            if(l>=mid+1) return querysum(rs,l,r);
            return querysum(ls,l,mid)+querysum(rs,mid+1,r);
        }

    }tree;

    void Build(int n){tree.build(1,1,n);}

    ll Querysum(int u,int v)
    {
        ll ans=0;
        while(N[u].top!=N[v].top)
        {
            if(N[N[u].top].dep<N[N[v].top].dep) swap(u,v);
            ans+=tree.querysum(1,N[N[u].top].dfn,N[u].dfn);
            u=N[N[u].top].fa;
        }
        if(N[u].dep>N[v].dep) swap(u,v);
        ans+=tree.querysum(1,N[u].dfn,N[v].dfn);
        return ans;
    }

    void Add(int u,int v,ll val)
    {
        while(N[u].top!=N[v].top)
        {
            if(N[N[u].top].dep<N[N[v].top].dep) swap(u,v);
            tree.add(1,N[N[u].top].dfn,N[u].dfn,val);
            u=N[N[u].top].fa;
        }
        if(N[u].dep>N[v].dep) swap(u,v);
        tree.add(1,N[u].dfn,N[v].dfn,val);
    }
}Tree;

int main()
{
    ios::sync_with_stdio(false);
    int n,m,r,p;
    cin>>n>>m>>r>>p;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        Tree.add(u,v);
    }
    Tree.split(r);
    Tree.Build(n);
    int a,u,v,val;
    for(int i=1;i<=m;i++)
    {
        cin>>a;
        if(a==1)
        {
            cin>>u>>v>>val;
            Tree.Add(u,v,val);
        }
        if(a==2)
        {
            cin>>u>>v;
            ll ans=Tree.Querysum(u,v);
            cout<<ans%p<<'\n';
        }
        if(a==3)
        {
            cin>>u>>val;
            Tree.tree.add(1,Tree.N[u].dfn,Tree.N[u].dfn+Tree.N[u].size-1,val);
        }
        if(a==4)
        {
            cin>>u;
            ll ans=Tree.tree.querysum(1,Tree.N[u].dfn,Tree.N[u].dfn+Tree.N[u].size-1);
            cout<<ans%p<<'\n';
        }
    }
    return 0;
}