Eternity

Until The End

树链剖分 & 树上差分

发表于 更新于 分类于 ，
本文字数： 41k 阅读时长 ≈ 37 分钟

“枷锁层深纵横，末路穷途糜烂。”

树链剖分

实质：将一棵树剖分成若干条链，并使用数据结构去优化维护，以达到 $\mathcal O(\log n)$ 的时间复杂度。是一些数据结构或者算法在树上的推广。

常用方法

轻重链剖分/启发式剖分

给出定义：将树分成轻边和重边，对于一个节点 $u$ 有函数 $size[u]$ 表示以 $u$ 为根节点的子树节点个数。那么有一个节点 $u$ 有 $\forall v,c(u,v)\in E$ ，而 $size[v]=\max\{size[u.son]\}$ ，则 $c(u,v)$ 为重边，而 $c(u,u.son),u.son\ne v$ 为轻边。

有下列性质：

  • $c’(u,v)$ 为轻边，则有 $size[v]\le \frac{size[u]}{2}$ ；
  • 从 $root$ 到任意一点的路径上，不超过 $\mathcal O(\log n)$ 条轻边数和重链数。

另外：

  • 重儿子：与父节点以重边相连的节点，也是子树节点最多的节点。
  • 重边：定义如上。
  • 重链：全部由重边构成的路径（一个节点也是一条重链）。
  • 轻儿子：一个节点除重儿子外的所有子节点。
  • 轻边：一个节点到其轻儿子的边。

img

有一个性质：

一棵树的重心一定在这棵树的重链（由根结点及其重儿子组成的链）上。

对于一个大小为 $n$ 的树与任意一个树中结点 $c$，称 $c$ 是该树的重心当且仅当在树中删去 $c$ 及与它关联的边后，分裂出的所有子树的大小均不超过 $\lfloor \frac{n}{2} \rfloor$（其中 $\lfloor x \rfloor$ 是下取整函数）。对于包含至少一个结点的树，它的重心只可能有 $1$ 或 $2$ 个。

节点信息

$fa[x]$ 表示 $x$ 的父节点。

$dep[x]$ 表示 $x$ 的深度。

$size[x]$ 表示以 $x$ 为根的子树的节点数。

$son[x]$ 表示 $x$ 的重儿子。

$top[x]$ 表示 $x$ 所在重链的顶部节点编号。

$seg[x]$ 表示 $x$ 在线段树中的编号（如果以线段树维护）。

$rev[x]$ 表示线段树中编号为 $x$ 的节点在原树中对应的节点编号。

操作

初始化

首先一遍 dfs(int x,int last) 处理出 $fa[],dep[],size[],son[]$ 等信息，类似于树型 dp 。

然后第二遍 dfs(int x,int last) 处理出 $seg[],top[],rev[]$ 等信息。

第一遍 $dfs$ ：

1
2
3
4
5
6
7
8
9
10
11
12
void dfsTree(int x,int last,int depth)
{
    Pt[x].size=1,Pt[x].fa=last;
    Pt[x].dep=depth;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x,depth+1);
        Pt[x].size+=Pt[v].size;
        if(Pt[v].size>Pt[Pt[x].son].size) Pt[x].son=v;
    }
}

第二遍 $dfs$ ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void dfsDfn(int x,int topf)
{
    Dfn[x]=++Cnt;		//树的dfs序，也就是映射到线段树内的编号
    Wgt[Cnt]=val[x];	//是排序之后对应的值，也就是映射到线段树内树的点权值
    Pt[x].top=topf;
    if(!Pt[x].son) return ;
    dfsDfn(Pt[x].son,topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        v=Edge[e].to;
        if(v==Pt[x].fa||v==Pt[x].son) continue;
        dfsDfn(v,v);	//每一个轻儿子都有一条从自己开始的重链
    }
}

映射

映射指的是将整个树链映射到所对应的数据结构内，可以是 BIT 或者 Segment Tree 甚至是 Splay 等平衡树，视题目而定。

线段树不太详解

接下来就是常规的线段树操作：

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
struct SegmentTree
{
    int val,size,tag,l,r;
}Tree[MAXN<<2];
inline void pushUp(int p)
{
    Tree[p].val=(Tree[p<<1].val+Tree[p<<1|1].val)%Mod;
}	//向上传递
inline void pushDown(int p)
{
    if(Tree[p].tag)
    {
        Tree[p<<1].val=(Tree[p<<1].val+Tree[p].tag*Tree[p<<1].size)%Mod;
        Tree[p<<1|1].val=(Tree[p<<1|1].val+Tree[p].tag*Tree[p<<1|1].size)%Mod;
        Tree[p<<1].tag=(Tree[p<<1].tag+Tree[p].tag)%Mod;
        Tree[p<<1|1].tag=(Tree[p<<1|1].tag+Tree[p].tag)%Mod;
        Tree[p].tag=0;
    }
}	//向下传递
void build(int p,int l,int r)
{
    Tree[p].l=l,Tree[p].r=r,Tree[p].size=r-l+1;
    if(l==r)
    {
        Tree[p].val=Wgt[l]%Mod;
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    pushUp(p);
}	//建树
void modifyAdd(int p,int l,int r,int d)
{
    if(l<=Tree[p].l&&Tree[p].r<=r)
    {
        Tree[p].val+=d*Tree[p].size;
        Tree[p].tag+=d;
        return ;
    }
    pushDown(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(l<=mid) modifyAdd(p<<1,l,r,d);
    if(mid<r) modifyAdd(p<<1|1,l,r,d);
    pushUp(p);
}	//区间修改
int queryAdd(int p,int l,int r)
{
    if(l<=Tree[p].l&&Tree[p].r<=r) return Tree[p].val;
    int mid=(Tree[p].l+Tree[p].r)>>1;
    int sum=0;
    pushDown(p);
    if(l<=mid) sum=(sum+queryAdd(p<<1,l,r))%Mod;
    if(mid<r) sum=(sum+queryAdd(p<<1|1,l,r))%Mod;
    return sum;
}	//区间查询

树链操作

如果你观察仔细，会发现一个非常神奇的特点：

在最后求出来的 $dfs$ 序内（也就是线段树的顺序），满足：

  • 任意一条重链内的节点编号连续；
  • 任意一棵子树内的节点编号连续。

岂不美哉。

路径查询与修改

因为任意重链内节点编号连续，那么对于路径 $(x,y)$ ，我们的首要任务是把 $x$ 和 $y$ 跳到同一条链中。（然后你会发现最后他们跳到了 $lca(x,y)$ 的链上）然后每跳一次，就把跳过的那条链修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
inline void modifyTreeAdd(int x,int y,int dz)
{
    while(Pt[x].top!=Pt[y].top)
    {
        if(Pt[Pt[x].top].dep<Pt[Pt[y].top].dep) swap(x,y);
        modifyAdd(1,Dfn[Pt[x].top],Dfn[x],dz);
        x=Pt[Pt[x].top].fa;
    }
    if(Pt[x].dep>Pt[y].dep) swap(x,y);
    modifyAdd(1,Dfn[x],Dfn[y],dz);
}	//路径修改
inline int queryTreeAdd(int x,int y)
{
    int res=0;
    while(Pt[x].top!=Pt[y].top)
    {
        if(Pt[Pt[x].top].dep<Pt[Pt[y].top].dep) swap(x,y);
        res=(res+queryAdd(1,Dfn[Pt[x].top],Dfn[x]))%Mod;
        x=Pt[Pt[x].top].fa;
    }
    if(Pt[x].dep>Pt[y].dep) swap(x,y);
    res=(res+queryAdd(1,Dfn[x],Dfn[y]))%Mod;
    return res;
}	//路经查询

子树查询与修改

既然子树节点也是连续的，那就更没什么说头了，直接一步解决即可。

1
2
3
4
modifyAdd(1,Dfn[x],Dfn[x]+Pt[x].size-1,z%Mod);
//子树修改
printf("%d\n",queryAdd(1,Dfn[x],Dfn[x]+Pt[x].size-1));
//子树查询

例题

模板题

路径修改，路径查询，子树修改，子树查询。

AC Code 
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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M,Root,Mod,val[MAXN];
struct Graph
{
    int next,to;
    Graph(int n=0,int t=0):next(n),to(t){}
}Edge[MAXN<<1];
struct Point
{
    int fa,dep,size,son,top;
}Pt[MAXN];
int Head[MAXN],Total;
int Dfn[MAXN<<2],Cnt,Wgt[MAXN<<2];
inline void addEdge(int u,int v)
{
    Edge[++Total]=Graph(Head[u],v);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u);Head[v]=Total;
}
void dfsTree(int x,int last,int depth)
{
    Pt[x].size=1,Pt[x].fa=last;
    Pt[x].dep=depth;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x,depth+1);
        Pt[x].size+=Pt[v].size;
        if(Pt[v].size>Pt[Pt[x].son].size) Pt[x].son=v;
    }
}
void dfsDfn(int x,int topf)
{
    Dfn[x]=++Cnt;
    Wgt[Cnt]=val[x];
    Pt[x].top=topf;
    if(!Pt[x].son) return ;
    dfsDfn(Pt[x].son,topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        v=Edge[e].to;
        if(v==Pt[x].fa||v==Pt[x].son) continue;
        dfsDfn(v,v);
    }
}
struct SegmentTree
{
    int val,size,tag,l,r;
}Tree[MAXN<<2];
inline void pushUp(int p)
{
    Tree[p].val=(Tree[p<<1].val+Tree[p<<1|1].val)%Mod;
}
inline void pushDown(int p)
{
    if(Tree[p].tag)
    {
        Tree[p<<1].val=(Tree[p<<1].val+Tree[p].tag*Tree[p<<1].size)%Mod;
        Tree[p<<1|1].val=(Tree[p<<1|1].val+Tree[p].tag*Tree[p<<1|1].size)%Mod;
        Tree[p<<1].tag=(Tree[p<<1].tag+Tree[p].tag)%Mod;
        Tree[p<<1|1].tag=(Tree[p<<1|1].tag+Tree[p].tag)%Mod;
        Tree[p].tag=0;
    }
}
void build(int p,int l,int r)
{
    Tree[p].l=l,Tree[p].r=r,Tree[p].size=r-l+1;
    if(l==r)
    {
        Tree[p].val=Wgt[l]%Mod;
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    pushUp(p);
}
void modifyAdd(int p,int l,int r,int d)
{
    if(l<=Tree[p].l&&Tree[p].r<=r)
    {
        Tree[p].val+=d*Tree[p].size;
        Tree[p].tag+=d;
        return ;
    }
    pushDown(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(l<=mid) modifyAdd(p<<1,l,r,d);
    if(mid<r) modifyAdd(p<<1|1,l,r,d);
    pushUp(p);
}
int queryAdd(int p,int l,int r)
{
    if(l<=Tree[p].l&&Tree[p].r<=r) return Tree[p].val;
    int mid=(Tree[p].l+Tree[p].r)>>1;
    int sum=0;
    pushDown(p);
    if(l<=mid) sum=(sum+queryAdd(p<<1,l,r))%Mod;
    if(mid<r) sum=(sum+queryAdd(p<<1|1,l,r))%Mod;
    return sum;
}
inline void modifyTreeAdd(int x,int y,int dz)
{
    while(Pt[x].top!=Pt[y].top)
    {
        if(Pt[Pt[x].top].dep<Pt[Pt[y].top].dep) swap(x,y);
        modifyAdd(1,Dfn[Pt[x].top],Dfn[x],dz);
        x=Pt[Pt[x].top].fa;
    }
    if(Pt[x].dep>Pt[y].dep) swap(x,y);
    modifyAdd(1,Dfn[x],Dfn[y],dz);
}
inline int queryTreeAdd(int x,int y)
{
    int res=0;
    while(Pt[x].top!=Pt[y].top)
    {
        if(Pt[Pt[x].top].dep<Pt[Pt[y].top].dep) swap(x,y);
        res=(res+queryAdd(1,Dfn[Pt[x].top],Dfn[x]))%Mod;
        x=Pt[Pt[x].top].fa;
    }
    if(Pt[x].dep>Pt[y].dep) swap(x,y);
    res=(res+queryAdd(1,Dfn[x],Dfn[y]))%Mod;
    return res;
}
int main()
{
    // freopen("tree-chain.in","r",stdin);
    // freopen("tree-chain.out","w",stdout);
    read(N,M,Root,Mod);
    for(int i=1;i<=N;++i) read(val[i]);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);
        addEdge(u,v);
    }
    dfsTree(Root,0,1);
    dfsDfn(Root,Root);
    build(1,1,N);
    for(int i=1,opt,x,y,z;i<=M;++i)
    {
        read(opt);
        if(opt==1)
        {
            read(x,y,z);
            modifyTreeAdd(x,y,z%Mod);
        }
        else if(opt==2)
        {
            read(x,y);
            printf("%d\n",queryTreeAdd(x,y));
        }
        else if(opt==3)
        {
            read(x,z);
            modifyAdd(1,Dfn[x],Dfn[x]+Pt[x].size-1,z%Mod);
        }
        else
        {
            read(x);
            printf("%d\n",queryAdd(1,Dfn[x],Dfn[x]+Pt[x].size-1));
        }
    }
    return 0;
}
/*
5 5 2 24
7 3 7 8 0 
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3

8 10 2 448348
458 718 447 857 633 264 238 944 
1 2
2 3
3 4
6 2
1 5
5 7
8 6
3 7 611
4 6
3 1 267
3 2 111
1 6 3 153
3 7 673
4 8
2 6 1
4 7
3 4 228
*/

最近公共祖先

裸裸的树剖，甚至不需要数据结构维护。

对于一组询问 $(x,y)$ 首先将两个点跳到同一条重链上，然后输出深度小的点即可。

另外，还是不建议用结构体来存储节点，读者可以比对一下这道题和上一道题的代码量，就会发现其实还是单数组的更好读和修改一些（个人意见）。

AC Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=5e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M,Root;
struct Graph
{
    int next,to;
    Graph(int n=0,int t=0):next(n),to(t){}
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=Graph(Head[u],v);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u);Head[v]=Total;
}
int Size[MAXN],Dep[MAXN],Top[MAXN],Fa[MAXN],Son[MAXN];
void dfsTree(int x,int last,int dep)
{
    Fa[x]=last,Size[x]=1,Dep[x]=dep;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x,dep+1);
        Size[x]+=Size[v];
        if(!Son[x]||Size[Son[x]]<Size[v]) Son[x]=v;
    }
}
void dfsDfn(int x,int topf)
{
    Top[x]=topf;
    if(!Son[x]) return ;
    dfsDfn(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        v=Edge[e].to;
        if(v==Fa[x]||v==Son[x]) continue;
        dfsDfn(v,v);
    }
}
inline int lca(int x,int y)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) swap(x,y);
        x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) swap(x,y);
    return x;
}
int main()
{
    // freopen("tree-chain.in","r",stdin);
    // freopen("tree-chain.out","w",stdout);
    read(N,M,Root);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);
        addEdge(u,v);
    }
    dfsTree(Root,0,1);
    dfsDfn(Root,Root);
    for(int i=1,x,y;i<=M;++i)
    {
        read(x,y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}
/*
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
*/

P3128

维护区间和，然后单点查找即可。

AC Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=5e4+1;
const int MAXK=1e5+1;
const int INF=0x7f7f7f7f;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,K;
struct Graph
{
    int next,to;
    Graph(int n=0,int t=0):next(n),to(t){}
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=Graph(Head[u],v);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u);Head[v]=Total;
}
int Dep[MAXN],Son[MAXN],Fa[MAXN],Size[MAXN];
void dfsTree(int x,int last)
{
    Dep[x]=Dep[last]+1;Size[x]=1;Fa[x]=last;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Size[x]+=Size[v];
        if(Size[v]>Size[Son[x]]||!Son[x]) Son[x]=v;
    }
}
int Dfn[MAXN],Top[MAXN],Cnt;
void dfsDfn(int x,int topf)
{
    Dfn[x]=++Cnt;
    Top[x]=topf;
    if(!Son[x]) return ;
    dfsDfn(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsDfn(v,v);
    }
}
struct SegmentTree
{
    int l,r,val,tag;
}Tree[MAXN<<2];
inline void pushUp(int p)
{
    Tree[p].val=Tree[p<<1].val+Tree[p<<1|1].val;
}
inline void pushDown(int p)
{
    if(Tree[p].tag)
    {
        Tree[p<<1].val+=(Tree[p<<1].r-Tree[p<<1].l+1)*Tree[p].tag;
        Tree[p<<1|1].val+=(Tree[p<<1|1].r-Tree[p<<1|1].l+1)*Tree[p].tag;
        Tree[p<<1].tag+=Tree[p].tag;
        Tree[p<<1|1].tag+=Tree[p].tag;
        Tree[p].tag=0;
    }
}
void build(int p,int l,int r)
{
    Tree[p].l=l,Tree[p].r=r;
    if(l==r)
    {
        Tree[p].val=Tree[p].tag=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    pushUp(p);
}
void modify(int p,int l,int r,int d)
{
    if(l<=Tree[p].l&&Tree[p].r<=r)
    {
        Tree[p].val+=(Tree[p].r-Tree[p].l+1)*d;
        Tree[p].tag+=d;
        return ;
    }
    pushDown(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(l<=mid) modify(p<<1,l,r,d);
    if(mid<r) modify(p<<1|1,l,r,d);
    pushUp(p);
}
int query(int p,int l,int r)
{
    if(l<=Tree[p].l&&Tree[p].r<=r) return Tree[p].val;
    int val=0;
    int mid=(Tree[p].l+Tree[p].r)>>1;
    pushDown(p);
    if(l<=mid) val+=query(p<<1,l,r);
    if(mid<r) val+=query(p<<1|1,l,r);
    return val;
}
inline void modifyPath(int x,int y,int d)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) swap(x,y);
        modify(1,Dfn[Top[x]],Dfn[x],d);
        x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) swap(x,y);
    modify(1,Dfn[x],Dfn[y],d);
}
int main()
{
    // freopen("tree-chain.in","r",stdin);
    // freopen("tree-chain.out","w",stdout);
    read(N,K);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);
        addEdge(u,v);
    }
    dfsTree(1,0);
    dfsDfn(1,1);
    build(1,1,N);
    for(int i=1,x,y;i<=K;++i)
    {
        read(x,y);
        modifyPath(x,y,1);
    }
    int ans=-INF;
    for(int i=1;i<=N;++i) ans=max(ans,query(1,Dfn[i],Dfn[i]));
    printf("%d",ans);
    return 0;
}
/*
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
*/

P3258

与上一题类似，可以说是双倍经验。

AC Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=3e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,Turn[MAXN];
struct Graph
{
    int next,to;
    Graph(int n=0,int t=0):next(n),to(t){}
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=Graph(Head[u],v);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u);Head[v]=Total;
}
int Fa[MAXN],Son[MAXN],Dep[MAXN],Size[MAXN];
void dfsTree(int x,int last)
{
    Fa[x]=last,Dep[x]=Dep[last]+1,Size[x]=1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Size[x]+=Size[v];
        if(!Son[x]||Size[v]>Size[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN],Dfn[MAXN],Cnt;
void dfsDfn(int x,int topf)
{
    Dfn[x]=++Cnt;
    Top[x]=topf;
    if(!Son[x]) return ;
    dfsDfn(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsDfn(v,v);
    }
}
struct SegmentTree
{
    int l,r,val,tag,size;
}Tree[MAXN<<2];
inline void pushUp(int p)
{
    Tree[p].val=Tree[p<<1].val+Tree[p<<1|1].val;
}
inline void pushDown(int p)
{
    if(Tree[p].tag)
    {
        Tree[p<<1].val+=Tree[p<<1].size*Tree[p].tag;
        Tree[p<<1|1].val+=Tree[p<<1|1].size*Tree[p].tag;
        Tree[p<<1].tag+=Tree[p].tag;
        Tree[p<<1|1].tag+=Tree[p].tag;
        Tree[p].tag=0;
    }
}
void build(int p,int l,int r)
{
    Tree[p].l=l,Tree[p].r=r,Tree[p].size=r-l+1;
    if(l==r)
    {
        Tree[p].val=Tree[p].tag=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    pushUp(p);
}
void modify(int p,int l,int r,int d)
{
    if(l<=Tree[p].l&&Tree[p].r<=r)
    {
        Tree[p].val+=d*Tree[p].size;
        Tree[p].tag+=d;
        return ;
    }
    pushDown(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(l<=mid) modify(p<<1,l,r,d);
    if(mid<r) modify(p<<1|1,l,r,d);
    pushUp(p); 
}
int query(int p,int l,int r)
{
    if(l<=Tree[p].l&&Tree[p].r<=r) return Tree[p].val;
    pushDown(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    int val=0;
    if(l<=mid) val+=query(p<<1,l,r);
    if(mid<r) val+=query(p<<1|1,l,r);
    return val;
}
inline void modifyPath(int x,int y,int d)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) swap(x,y);
        modify(1,Dfn[Top[x]],Dfn[x],d);
        x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) swap(x,y);
    modify(1,Dfn[x],Dfn[y],d);
}
int main()
{
    // freopen("tc.in","r",stdin);
    // freopen("tc.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(Turn[i]);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);
        addEdge(u,v);
    }
    dfsTree(Turn[1],0);
    dfsDfn(Turn[1],Turn[1]);
    build(1,1,N);
    for(int i=1;i<=N-1;++i)
    {
        modifyPath(Turn[i+1],Turn[i+1],-1);
        modifyPath(Turn[i],Turn[i+1],1);
    }
    for(int i=1;i<=N;++i)
        printf("%d\n",query(1,Dfn[i],Dfn[i]));
    return 0;
}
/*
5
1 4 5 3 2
1 2
2 4
2 3
4 5
*/

边权挂点

我们知道，树剖的实质是维护点权的，但是，树剖也可以进行一系列操作使其能够维护边权。俗称边权挂点。

我们把题目的树视作有根树，每一个节点都只存在至多 $1$ 个父亲。那么，我们将原来维护 $u$ 节点的 $dfn[u]$ 指向 $c(fa[u],u)$ 的权值。通俗地讲，维护该点与其父节点的边。

但是，维护边权时有许多需要注意的。在我们已经跳到了同一重链中，以边权和为例，对于 $lca(x,y)$ 而言，维护的是 $c(fa[lca(x,y)],lca(x,y))$ 的权值，但事实上，我们在求解 $\sum\limits^{e\in path(x,y)}_{e}e(u,v)$ 时，不会去求 $lca(x,y)$ 与其父节点的边权。那么，我们在 $dfn[x]$ 的地方 $+1$ 使其跳过 $lca(x,y)$ 即可。

但是，这并不是普遍情况，真正需要 +1 还是需要 -1 要视题目而定，所以为什么树剖的边权题非常难调，调得人想趋势。

给出一道比较模板的边权挂点题

AC Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=2e5+1;
const int MAXM=2e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M;
struct Graph
{
    int next,to;
    ll val;
    Graph(int n=0,int t=0,ll v=0):next(n),to(t),val(v){}
}Edge[MAXM<<1];
int Head[MAXN],Total,Xor[MAXN];
inline void addEdge(int u,int v,ll w)
{
    Edge[++Total]=Graph(Head[u],v,w);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u,w);Head[v]=Total;
}
int Dep[MAXN],Son[MAXN],Fa[MAXN],Size[MAXN],Top[MAXN];
void dfsTree(int x,int last,int dep)
{
    Fa[x]=last,Dep[x]=dep,Size[x]=1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        Xor[v]=Edge[e].val;
        dfsTree(v,x,dep+1);
        Size[x]+=Size[v];
        if(!Son[x]||Size[v]>Size[Son[x]]) Son[x]=v;
    }
}
int Dfn[MAXN],Val[MAXN],Cnt;
void dfsDfn(int x,int topf)
{
    Dfn[x]=++Cnt;
    Val[Cnt]=Xor[x];Top[x]=topf;
    if(!Son[x]) return ;
    dfsDfn(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||Edge[e].to==Son[x]) continue;
        dfsDfn(v,v);
    }
}
struct SegmentTree
{
    int l,r,val;
}Tree[MAXN<<1];
inline void pushUp(int p)
{
    Tree[p].val=Tree[p<<1].val^Tree[p<<1|1].val;
}
void build(int p,int l,int r)
{
    Tree[p].l=l,Tree[p].r=r;
    if(l==r)
    {
        Tree[p].val=Val[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    pushUp(p);
}
int queryXor(int p,int l,int r)
{
    if(l<=Tree[p].l&&Tree[p].r<=r) return Tree[p].val;
    int mid=(Tree[p].l+Tree[p].r)>>1;
    int val=0;
    if(l<=mid) val^=queryXor(p<<1,l,r);
    if(mid<r) val^=queryXor(p<<1|1,l,r);
    return val;
}
inline int queryPath(int x,int y)
{
    if(x==y) return 0;
    int ans=0;
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) swap(x,y);
        ans^=queryXor(1,Dfn[Top[x]],Dfn[x]);
        x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) swap(x,y);
    ans^=queryXor(1,Dfn[x]+1,Dfn[y]);
    return ans;
}
int main()
{
    // freopen("tree-chain.in","r",stdin);
    // freopen("tree-chain.out","w",stdout);
    read(N);
    for(int i=2,u,v,w;i<=N;++i)
    {
        read(u,v,w);
        addEdge(u,v,w);
    }
    dfsTree(1,0,1);
    dfsDfn(1,1);
    build(1,1,N);
    read(M);
    for(int i=1,x,y;i<=M;++i)
    {
        read(x,y);
        printf("%d\n",queryPath(x,y));
    }
    /*for(int i=1;i<=N;++i) printf("%d ",Dfn[i]);
    puts("");
    for(int i=1;i<=N;++i) printf("%d ",Val[i]);*/
    return 0;
}
/*
5
1 4 9644
2 5 15004
3 1 14635
5 3 9684
3
2 4
5 4
1 1
*/

树上 k 级祖先

然后发现这道题的长链剖分还没有重链剖分跑得快。

先说常用的重链剖分的写法：

因为点 $u$ 的祖先一定在它所属的链之上，而链的 $\text{dfn}$ 序是相连的，所以我们依然可以选择跳链。这样的做法摊下来只有 $\text{3.12s}$ ，跑进了前五。

AC Code 
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
#include<bits/stdc++.h>
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
const int MAXN=5e5+10;
int N,Q,Root;
long long ans;
#define ui unsigned int
ui Seed,lastans;
inline ui get(ui x)
{
	x^=x<<13;
	x^=x>>17;
	x^=x<<5;
	return Seed=x; 
}
struct LTC
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(LTC){Head[u],v};Head[u]=Total;
    Edge[++Total]=(LTC){Head[v],u};Head[v]=Total;
}
int Siz[MAXN],Dep[MAXN],Fa[MAXN],Son[MAXN];
void dfsTree(int x,int last)
{
    Siz[x]=1,Dep[x]=Dep[last]+1,Fa[x]=last;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Siz[x]+=Siz[v];
        if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN],Dfn[MAXN],Bck[MAXN],Cnt;
void dfsChain(int x,int topf)
{
    Dfn[x]=++Cnt,Top[x]=topf;
    Bck[Cnt]=x;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsChain(v,v);
    }
}
inline int kthLca(int x,int k)
{
    while(k>=Dfn[x]-Dfn[Top[x]]+1&&x!=Root)
    {
        k-=(Dfn[x]-Dfn[Top[x]]+1);
        x=Fa[Top[x]];
    }
    return Bck[Dfn[x]-k];
}
int main()
{
    read(N,Q,Seed);
    for(int i=1,fa;i<=N;++i)
    {
        read(fa);
        if(!fa) Root=i;
        else addEdge(fa,i);
    }
    dfsTree(Root,0);
    dfsChain(Root,Root);
    for(int i=1;i<=Q;++i)
    {
        int Qx=(get(Seed)^lastans)%N+1;
        int Qk=(get(Seed)^lastans)%Dep[Qx];
        ans^=1ll*i*(1ll*(lastans=kthLca(Qx,Qk)));
        // printf("%d %d %d\n",Qx,Qk,lastans);
    }
    printf("%lld",ans);
    return 0;
}
/*
6 3 7
5 5 2 2 0 3
*/

而对于长链剖分，规定长儿子为其儿子深度最大的点。然后剖，跳即可。贺完了也没理太清楚，之后学 $\text{dp}$ 优化的时候再学一下。

长链剖分的时间是 $\text{5.45s}$ 。

AC Code 
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
#include<bits/stdc++.h>
const int MAXN=5e5+10;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T x,T y)
{
    return x>y?1:0,x=y;
}
int N,Q,Root=1;
#define ui unsigned int
ui Seed;
inline ui get(ui x)
{
	x^=x<<13;
	x^=x>>17;
	x^=x<<5;
	return Seed=x; 
}
struct LTC
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(LTC){Head[u],v};Head[u]=Total;
    // Edge[++Total]=(LTC){Head[v],u};Head[v]=Total;
}
int Fa[MAXN][21];
int Son[MAXN],Top[MAXN];
int Hig[MAXN],Dep[MAXN],Dfn[MAXN],Bck[MAXN],Up[MAXN];
int Log[MAXN],Cnt;
void dfsTree(int x)
{
    for(int i=1;i<=20;++i) Fa[x][i]=Fa[Fa[x][i-1]][i-1];
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        v=Edge[e].to;
        Dep[v]=Hig[v]=Dep[x]+1;
        dfsTree(v);
        Hig[x]=std::max(Hig[x],Hig[v]);
        if(Hig[v]>Hig[Son[x]]) Son[x]=v;
    }
}
void dfsChain(int x,int topf)
{
    Dfn[x]=++Cnt;Bck[Cnt]=x;
    Up[Cnt]=topf;
    if(Son[x])
    {
        Top[Son[x]]=Top[x];
        dfsChain(Son[x],Fa[topf][0]);
    }
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Son[x]) continue;
        Top[v]=v;
        dfsChain(v,v);
    }
}
inline int lcaKth(int x,int k)
{
    if(!k) return x;
    x=Fa[x][Log[k]],k-=(1<<Log[k]);
    k-=Dep[x]-Dep[Top[x]],x=Top[x];
    if(k>=0) return Up[Dfn[x]+k];
    return Bck[Dfn[x]-k];
}
int main()
{
    read(N,Q,Seed);
    for(int i=1,fa;i<=N;++i)
    {
        read(fa);
        if(!fa) Root=i;
        else addEdge(fa,i);
        Fa[i][0]=fa;
    }
    Log[0]=-1;
    for(int i=1;i<=N;++i) Log[i]=Log[i>>1]+1;
    Dep[Root]=1;dfsTree(Root);
    Top[Root]=Root;dfsChain(Root,Root);
    long long ans=0,lastans=0;
    for(int i=1;i<=Q;++i)
    {
        int Qx=(get(Seed)^lastans)%N+1;
        int Qk=(get(Seed)^lastans)%Dep[Qx];
        ans^=1ll*i*1ll*(lastans=lcaKth(Qx,Qk));
        // printf("%d %d %d\n",Qx,Qk,lastans);
    }
    write(ans);
    return 0;
}
/*
6 3 7
5 5 2 2 0 3
*/

换根树剖

分类讨论即可。

没写，贺了。

树上差分

实质：在树上进行差分约束。

差分

差分的思想，其实是前缀的逆运算。设原数列为 $a$ ，则定义前缀和 $sum[i]=\sum_{j=1}^{i}a_j$ ，而差分数组 $diff[i]=a_i-a_{i-1}$ 。

我们可以看一个例子：

$a=\{1,3,2,8,4,6\}$

则有：

$sum=\{1,4,6,14,18,24\}$

$diff=\{1,2,-1,6,-4,2\}$

然后我们来处理差分数组的前缀和得到：

$diff_{sum}=\{1,3,2,8,4,6\}$

并处理前缀数组的差分：

$sum_{diff}=\{1,3,2,8,4,6\}$

那么，结论显然，前缀和与差分约束是逆运算，且前缀的差分和差分的前缀都是原数列。

树上差分

树上差分用于解决询问某个点或者某条边被经过的次数，则树上差分就会派上用场。且和树链剖分一样可以解决对树上路径的操作与询问。

在树状数组钟我们也提及过，使用差分约束，可以从修改区间优化到修改结点。这个思路也同样用到树上差分，利用差分的性质，对路径上的重要结点进行修改以避免暴力区间修改。在最后，使用 $dfs$ 遍历求出该树的 $dfs$ 序之后求出 $diff$ 的前缀和即可。

前汁芝士只有 $\text{LCA}$ ，当然，也可以联动树链剖分一起理解。

另外，差分修改操作的时间复杂度是 $\mathcal O(1)$ 的。

点差分

给一个操作，将 $(u,v)$ 之间的路径点权值加上 $w$ ，令 $o=lca(u,v),p=fa(o)$ ，那么，操作如下：

1
diff[u]+=w,diff[v]+=w,diff[o]-=w,diff[p]-=w;

每一个点的最后的点权就是以该点为根的子树的 $diff$ 和。读者可以自行去模拟几个例子。

边差分

与树链剖分的边权挂点思路一样，每一个点 $i$ 所表示的边权是 $(fa[i],i)$ 这条边的边权。

那么，同样，我们将 $(u,v)$ 之间的边权值加上 $w$ ，令 $o=lca(u,v)$ ，则有：

1
diff[u]+=w,diff[v]+=w,diff[o]-=2*w;

那么……没什么好讲的了。

树上差分能做的题和树链剖分是差不多的，只是看哪一个写起来方便简单。

例题

P1083

P1083 [NOIP2012 提高组] 借教室

这道题跟树没关系，单纯的差分约束而已。

我们选择二分 $m$ ，然后暴力加取 $1\sim mid$ 的差分，然后每一次检验暴力查询每一天是否合法，总的时间复杂度为 $\mathcal O(n\log m)$ 。

AC Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
const int MAXN=1e6+5;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
ll N,M,Rest[MAXN],L[MAXN],R[MAXN],S[MAXN],Diff[MAXN],Sum[MAXN];
inline bool check(int x)
{
    memset(Sum,0,sizeof(Sum));
    memset(Diff,0,sizeof(Diff));
    for(int i=1;i<=x;++i) Diff[L[i]]+=S[i];
    for(int i=1;i<=x;++i) Diff[R[i]+1]-=S[i];
    for(int i=1;i<=N;++i)
    {
        Sum[i]=Sum[i-1]+Diff[i];
        if(Sum[i]>Rest[i]) return 0;
    }
    return 1;
}
int main()
{
    // freopen("diff-con.in","r",stdin);
    // freopen("diff-con.out","w",stdout);
    read(N,M);
    for(re int i=1;i<=N;++i) read(Rest[i]);
    for(int i=1;i<=M;++i) read(S[i],L[i],R[i]);
    if(check(M)) putchar('0');
    else
    {
        int l=0,r=M;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(check(mid)) l=mid+1;
            else r=mid;
        }
        puts("-1"),write(l);
    }
    return 0;
}
/*
4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4
*/

P5542

二维差分。

前缀和公式：

1
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]

对于差分公式，需要视题目而定，有些题需要考虑边界，而有些不会。对于这道题则是：

1
dif[x1+1][y1+1]++,dif[x1+1][y2+1]--,dif[x2+1][y1+1]--,dif[x2+1][y2+1]++;
AC Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
const int MAXS=1001;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,K,ans;
int Dif[MAXS][MAXS];
int main()
{
    // freopen("2-diff.in","r",stdin);
    // freopen("2-diff.out","w",stdout);
    read(N,K);
    for(int i=1,x1,x2,y1,y2;i<=N;++i)
    {
        read(x1,y1,x2,y2);
        ++Dif[x1+1][y1+1];++Dif[x2+1][y2+1];--Dif[x1+1][y2+1];--Dif[x2+1][y1+1];
    }
    for(int i=1;i<=1000;++i)
        for(int j=1;j<=1000;++j)
        {
            Dif[i][j]=Dif[i][j]+Dif[i][j-1]+Dif[i-1][j]-Dif[i-1][j-1];
            if(Dif[i][j]==K) ++ans;
        }
    write(ans)/*,puts("")*/;
    /*for(int i=1;i<=10;++i)
    {
        for(int j=1;j<=10;++j) write(Dif[i][j]),putchar(' ');
        puts("");
    }*/
    return 0;
}
/*
3 2
1 1 5 5
4 4 7 6
3 3 8 7
*/

P3128

P3128 [USACO15DEC]Max Flow P

这道题同样可以使用树链剖分做，但现在我们试着用树上差分做。

这是一道常规的点差分模板题，直接修改加 $1$ 和减 $1$ 就可以了。不过我的 $\text{LCA}$ 还是用了树剖。但时间还是纯树剖不能想的。

AC Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
const int MAXN=5e4+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,K,ans;
struct DT
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(DT){Head[u],v};Head[u]=Total;
    Edge[++Total]=(DT){Head[v],u};Head[v]=Total;
}
int Diff[MAXN],Son[MAXN],Fa[MAXN],Dep[MAXN],Size[MAXN];
void dpTree(int x,int last)
{
    Dep[x]=Dep[last]+1,Fa[x]=last,Size[x]=1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dpTree(v,x);
        Size[x]+=Size[v];
        if(!Son[x]||Size[v]>Size[Son[x]]) Son[x]=v;
    }
}
int Dfn[MAXN],Top[MAXN],Cnt;
void dpChain(int x,int topf)
{
    Dfn[x]=++Cnt,Top[x]=topf;
    if(!Son[x]) return ;
    dpChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dpChain(v,v);
    }
}
inline int lca(int x,int y)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
        x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) std::swap(x,y);
    return x;
}
int main()
{
    // freopen("diff-tree.in","r",stdin);
    // freopen("diff-tree.out","w",stdout);
    read(N,K);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);addEdge(u,v);
    }
    dpTree(1,0),dpChain(1,1);
    for(int i=1,x,y;i<=K;++i)
    {
        read(x,y);
        int Lca=lca(x,y);
        ++Diff[Dfn[x]],++Diff[Dfn[y]],--Diff[Dfn[Lca]],--Diff[Dfn[Fa[Lca]]];
    }
    for(int i=1;i<=N;++i) Diff[i]+=Diff[i-1];
    for(int i=1;i<=N;++i) ans=std::max(ans,Diff[Dfn[i]+Size[i]-1]-Diff[Dfn[i]-1]);
    write(ans);
    return 0;
}
/*
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
*/

CF191C

边差分模板题。

可以理解一下统计答案操作，实际上的答案应该是整个子树的差分和，所以写成

1
Diff[Dfn[i]+Siz[i]-1]-Diff[Dfn[i]-1]

这样统计的原因和树链剖分的子树修改是一个道理。

AC Code 
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
const int MAXN=1e5+10;
int N,Q;
struct TC
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(TC){Head[u],v};Head[u]=Total;
    Edge[++Total]=(TC){Head[v],u};Head[v]=Total;
}
int Fa[MAXN],Siz[MAXN],Son[MAXN],Dep[MAXN];
void dfsTree(int x,int last)
{
    Fa[x]=last,Siz[x]=1,Dep[x]=Dep[last]+1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Siz[x]+=Siz[v];
        if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN],Dfn[MAXN],Cnt;
void dfsChain(int x,int topf)
{
    Top[x]=topf,Dfn[x]=++Cnt;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Son[x]||v==Fa[x]) continue;
        dfsChain(v,v);
    }
}
inline int getLca(int x,int y)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
        x=Fa[Top[x]];
    }
    return Dep[x]>Dep[y]?y:x;
}
int Diff[MAXN];
struct Edges
{
    int u,v,ans;
}Ed[MAXN];
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);addEdge(u,v);
        Ed[i-1]=(Edges){u,v};
    }
    dfsTree(1,0),dfsChain(1,1);
    read(Q);
    for(int i=1;i<=N-1;++i)
    {
        auto &e=Ed[i];
        if(Fa[e.u]==e.v) e.ans=e.u;
        else e.ans=e.v;
    }
    for(int u,v;Q--;)
    {
        read(u,v);
        int o=getLca(u,v);
        ++Diff[Dfn[u]],++Diff[Dfn[v]],Diff[Dfn[o]]-=2;
    }
    for(int i=1;i<=N;++i) Diff[i]+=Diff[i-1];
    for(int i=1;i<=N-1;++i) write(Diff[Dfn[Ed[i].ans]+Siz[Ed[i].ans]-1]-Diff[Dfn[Ed[i].ans]-1],' ');
    return 0;
}
/*
5
1 2
1 3
2 4
2 5
2
1 4
3 5
*/

P2680

这是一道较为进阶的树上差分。我们要求此时所有运输的时间最大值最小。这样就会想到去二分时间，然后用 $\mathcal O(m)$ 的时间去判断减去一条边之后是否能达到给出的时间。

然后就是查找 $\text{LCA}$ ，我还是选择了树剖，似乎这道题的倍增会被卡，不过幸好我不会。（有生以来树剖的预处理居然写炸了）

AC Code 
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
typedef long long ll;
const int MAXN=3e5+1;
const int INF=0x3f3f3f3f;
int N,M,Pte[MAXN];
struct TC
{
    int next,to,val;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(TC){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(TC){Head[v],u,w};Head[v]=Total;
}
int Fa[MAXN],Dep[MAXN],Size[MAXN],Son[MAXN],Dist[MAXN];
void dpTree(int x,int last)
{
    Dep[x]=Dep[last]+1,Fa[x]=last,Size[x]=1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        Dist[v]=Dist[x]+Edge[e].val;
        dpTree(v,x);
        Size[x]+=Size[v];
        if(!Son[x]||Size[v]>Size[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN];
void dpChain(int x,int topf)
{
    Top[x]=topf;
    if(!Son[x]) return ;
    dpChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dpChain(v,v);
    }
}
inline int getLca(int x,int y)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
        x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) std::swap(x,y);
    return x;
}
int Diff[MAXN],PathW;
int X[MAXN],Y[MAXN],Dis[MAXN],Lca[MAXN];
void getSum(int x,int last)
{
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        getSum(v,x);
        Diff[x]+=Diff[v];
    }
}
inline bool check(int x)
{
    /*printf("%d\n",x);*/
    memset(Diff,0,sizeof(Diff));
    int cnt=0,Max=-INF;
    for(int i=1;i<=M;++i)
        if(Dis[i]>x)
        {
            ++Diff[X[i]],++Diff[Y[i]],Diff[Lca[i]]-=2;
            Max=std::max(Max,Dis[i]-x);++cnt;
        }
    if(cnt==0) return 1;
    getSum(1,0);
    /*for(int i=1;i<=N;++i) printf("%d ",Diff[i]);
    printf("\n%d\n",cnt);*/
    for(int i=2;i<=N;++i) if(Diff[i]==cnt&&Dist[i]-Dist[Fa[i]]>=Max) return 1;
    return 0;
}
int main()
{
    // freopen("tree-chain-diff.in","r",stdin);
    // freopen("tree-chain-diff.out","w",stdout);
    read(N,M);
    for(int i=2,u,v,w;i<=N;++i)
    {
        read(u,v,w);addEdge(u,v,w);
        PathW+=w;
    }
    dpTree(1,0),dpChain(1,1);
    for(int i=1,x,y;i<=M;++i)
    {
        read(X[i],Y[i]);Lca[i]=getLca(X[i],Y[i]);
        Dis[i]=Dist[X[i]]+Dist[Y[i]]-(Dist[Lca[i]]*2);
    }
    int l=0,r=PathW,ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    write(ans);
    return 0;
}
/*
6 3 
1 2 3 
1 6 4 
3 1 7 
4 3 6 
3 5 5 
3 6 
2 5 
4 5
*/
相关文章