What is tree chain segmentation/heavy chain segmentation
We can find an example:
Now give one\(n（1 \le n \le 10^5）\)The tree of nodes, there is a value on each node, and now you can perform $m ( 1 \le m \le 10^5) $ operations. The format is as follows:
-
1 x zIndicates that\(x\)arrive\(y\)Add the node value on the shortest path\(z\) 。 -
2 x yExpress tree request\(x\)arrive\(y\)The sum of weights on the shortest path. -
3 x yPut the subtree\(x\)The weight of each node under\(y\) 。 -
4 xChildren's Tree\(x\)The sum of weights of each node below.
How to write it? Of course, you need pre-knowledgeLine segment tree. Next, let me tell you slowly.
Start by constructing a perfect array of fractions
We know that a tree can be constructed into a sequence through DFS, where for any subtree (including the root node), we call its number of nodes\(siz\). Subtree\(x\)The size is\(siz_x\). So how does this help in the secting? For a tree, DFS sequence is as follows:
1
/ \
2 3
/
4
\
5
Then after DFS, the sequence is as follows:
1 2 4 5 3
You can see the subtree\(x\)arrive\(x+siz_x\), the whole subtree\(x\). We temporarily call this array a fractional array\(tag\). But this is not the best. Sometimes it cannot guarantee the rules explained above. What should I do at this time? We can analyze it, in this tree,\(1\)There are two children,\(2\)and\(3\),and\(2\)The subtree size ratio\(3\)Big, then we stipulate\(2\)yes\(1\)ofHeavy children. from\(1\)arrive\(2\)We call this edgeHeavy chain. It can be seen that for any non-leaf node, there are unique heavy children, so we can construct the order of DFS based on the heavy children, because we give priority to traversing all heavy children in a tree, so all heavy children must be connected together. The above is an explanation. So what are the benefits of starting with a child who is more serious? We know that if we start traversing this array from a light child, the time complexity may reach\(O(n)\)(See later). But if you start with a heavy child, it will be different. We can prove that the time complexity can come\(O(\log^2n)\)The complexity of a single inquiry is proved as follows:
For nodes\(u\), it values children\(v\)Must be among all childrenThe largest subtreeThe one, that is:
Because of the size of a child's subtree\(\ge\)All other child nodes have subtree size, so for any light child\(w\)have:
And because the number of subtrees of all nodes +1 is equal to the number of nodes contained in its father node (a bit difficult to talk about), that is:
According to the second and three theorems above, solving the inequality equation can result in:
So we can know: **If a light child node\(w\)The subtree size is greater than\(\frac{1}{2} size(u)\), then the above theorem is not valid and violates the definition of valuing children, so there must be any arbitrary\(w\)：
Therefore, when you get the path from the root node to any node, at most, there is only one\(O(\log n)\)Light edge (because every time I touch the light edge, the size of the subtree will be seen as the original \frac{1}{2}, so at most\(\log^2n\)It will reach the root node)
And because heavy children are a continuous interval, it is enough to modify the line segment tree at one time, and the light side modification is every time\(O(\log n)\),most\(\log n\), so\(O(\log n)\)Time complexity is proven.
At this point, the key part of our tree chain segmentation has been completed.
Code is as follows:
void dfs1(int root, int fa) {
fath[root] = fa;
siz[root] = 1;
dep[root] = dep[fa] + 1;
for(auto i : tree[root]) {
if(i == fa) continue;
dfs1(i, root);
siz[root] += siz[i];
if(siz[i] > siz[son[root]])
son[root] = i;
}
}
void dfs2(int root, int tp) {
top[root] = tp;
dfn[root] = ++cnt;
rev[cnt] = root;
if(!son[root]) return;
dfs2(son[root], tp);
for(auto i : tree[root]) {
if(i == fath[root] || i == son[root]) continue;
dfs2(i, i);
}
}
insizIt means size,topIndicates the chain head (see later),dfnIndicates for\(root\)Node, position in the fractionation array.revIt's antidfn，cntGlobal counter,sonRecord the child number,depIndicates depth.
Use the idea of linked lists to complete the query/modification of perfect
We already know how to divide an effective fragmentation array. I just can't use it, what should I do?
Or take out a tree:
1
/ \
2 5
/ \ \
3 7 6
\ /
4 8
/ \
9 10
The constructed sequence is as follows (-Represents heavy chain, Indicates light edge)
1-2-3-4-9 10 7 5-6-8
Now we will\(10\)arrive\(8\)The process between the two is as follows:
- First make the heads of all heavy chains the smallest depth node, for example\(8,6,5\)The chain heads are\(5\)，\(9,4,3,2,1\)The chain heads are\(1\)
- All the light edges of the chain are themselves
Then when modifying, select a bar with a large depth each time until the two chain heads are the same. Then only the current one needs to be modified\(\min{u,v}\)arrive\(\max{u,v}\)(Two endpoints of inquiry/operation) is all right! .
We can also know here. If we look at it lightly, the time complexity is\(O(n)\)Yes. Be careful!
Because the query and modification code are similar, I will not write it in detail.
Code For Luogu P3384
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+100;
int num[maxn],fath[maxn],top[maxn],son[maxn],dep[maxn],siz[maxn];
int lay[maxn<<2],w[maxn<<2],tag1[maxn],tag2[maxn],cnt,n,m,r,p;
vector<vector<int> > tree;
inline void dfs1(int root,int fa){
fath[root]=fa;
siz[root]=1;
dep[root]=dep[fa]+1;
for(auto i : tree[root]){
if(i == fa)continue;
dfs1(i,root);
siz[root]+=siz[i];
if(siz[i]>siz[son[root]])
son[root]=i;
}
}
inline void dfs2(int root,int Top){
tag1[root]=++cnt;
tag2[cnt]=root;
top[root]=Top;
if(son[root]){
dfs2(son[root],Top);
for(auto i : tree[root]){
if(i == son[root] || i==fath[root])continue;
dfs2(i,i);
}
}
}
void pushup(int root){
w[root]=(w[root<<1]+w[root<<1|1])%p;
}
void maketag(int root,int l,int r,int lz){
lay[root]=(lay[root]+lz)%p;
w[root]=(w[root]+(r-l+1)*lz)%p;
}
void pushdn(int root,int l,int r){
if(lay[root]==0 || l==r) return;
int mid=(l+r)>>1;
maketag(root<<1,l,mid,lay[root]);
maketag(root<<1|1,mid+1,r,lay[root]);
lay[root]=0;
}
void build(int root,int l,int r){
if(l==r){
w[root]=num[tag2[l]]%p;
return ;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
pushup(root);
}
int query(int root,int l,int r,int L,int R){
if(R<l || L>r) return 0;
if(L<=l && r<=R) return w[root];
pushdn(root,l,r);
int mid=(l+r)>>1;
return (query(root<<1,l,mid,L,R)+query(root<<1|1,mid+1,r,L,R))%p;
}
void update(int root,int l,int r,int L,int R,int val){
if(R<l || L>r) return;
if(L<=l && r<=R){
maketag(root,l,r,val);
return;
}
pushdn(root,l,r);
int mid=(l+r)>>1;
update(root<<1,l,mid,L,R,val);
update(root<<1|1,mid+1,r,L,R,val);
pushup(root);
}
void udp(int x,int y,int val){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
update(1,1,n,tag1[top[x]],tag1[x],val);
x=fath[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
update(1,1,n,tag1[x],tag1[y],val);
}
int qry(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=(ans+query(1,1,n,tag1[top[x]],tag1[x]))%p;
x=fath[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans=(ans+query(1,1,n,tag1[x],tag1[y]))%p;
return ans;
}
signed main(){
ios::sync_with_stdio(false);
(0);
(0);
cin>>n>>m>>r>>p;
(n+1);
for(int i=1;i<=n;i++) cin>>num[i];
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
tree[x].push_back(y);
tree[y].push_back(x);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
for(int i=1;i<=m;i++){
int op,x,y,z;
cin>>op;
if(op==1){
cin>>x>>y>>z;
udp(x,y,z);
}
else if(op==2){
cin>>x>>y;
cout<<qry(x,y)<<endl;
}
else if(op==3){
cin>>x>>z;
update(1,1,n,tag1[x],tag1[x]+siz[x]-1,z);
}
else if(op==4){
cin>>x;
cout<<query(1,1,n,tag1[x],tag1[x]+siz[x]-1)<<endl;
}
}
return 0;
}
Please learn the line segment tree part by yourself!
Perfect exercises
- P3384 【Template】Heavy Chain Separation/Tree Chain Separation
- P3258 [JLOI2014] Squirrel's new home