2022.4.10#树链剖分=链式前向星+dfs序+lca思想+线段树

本文主要是介绍2022.4.10#树链剖分=链式前向星+dfs序+lca思想+线段树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

2022-04-10

树链剖分，理解完只有惊叹。

前置知识：

链式前向星：

需要的变量：

cnt 记录边数

edges{ to,w,next}的数组，存储边

head[maxn]存储每个节点的最新的那条边

 1 //链式前向星，储存图的方式，思想是前向
 2 //相当于一个邻接表的每一行的链表，向最前端插入
 3 
 4 #include<iostream>
 5 #define maxn 4000010
 6 using namespace std;
 7 typedef struct star{
 8     int to;//这条边的终点
 9     int w;//这条边的权值
10     int next;//上一条同起点边，的编号
11 }edges;
12 edges e[maxn];//存储的是第几个节点，即第几条边
13 int cnt=0;//记录边数
14 int head[maxn]={0};//存储每一个起点的最新的那条边，的编号
15 void add(int u,int v,int w)
16 {
17     cnt++;
18     e[cnt].to=v;
19     e[cnt].w=w;
20     e[cnt].next=head[u];//向前插入的过程
21     head[u]=cnt;
22 }
23 void display(int u)
24 {
25     for(int i=head[u];i!=0;i=e[i].next)
26     cout<<u<<" "<<e[i].to<<" "<<e[i].w<<endl;
27 }

dfs序思想：

需要：

times 时间戳，按找dfs的顺序给节点编号

dfn[]存储每个时间戳的节点编号

dfni[] dfn序的逆，知道节点编号来推得时间戳

为什么需要呢？因为我们建立线段树是根据时间戳的顺序建立的，为什么后面再讲，然后我build的时候，需要dfn来把tree[root]和某个时间戳对应的节点值联系上。

我query的时候，知道个节点，要转换成时间戳形式，来使用线段树，故dfni也是必要的。

size[] 存储每个节点的子树大小，因为dfs序有个独特的性质，那就是每个节点的子树的时间戳都是连续的，当解决一棵树上，对于一个节点的所有子树结点操作，的问题时，可以把树变成一个具有连续区间的链，故而使用美丽的线段树进行维护，这，就是dfs序的本质用法。

 1 ll dfn[maxn],dfni[maxn],times=0,size[maxn];
 2 void dfs(ll pre,ll fa)
 3 {
 4     if(first[pre]==0)
 5     return;
 6     else
 7     {
 8         times++;
 9         dfn[times]=pre;
10         dfni[pre]=times;
11         size[pre]=1;
12     }
13     for(ll i=first[pre];i!=0;i=edges[i].next)
14     {
15         if(edges[i].to!=fa)
16         {
17             dfs(edges[i].to,pre);
18             size[pre]+=size[edges[i].to];
19         }
20     }
21 }

lca思想：

然而，当我们需要求的是树上，任意的两个点的最短路径的操作时，dfs序就不起作用了。

这时候引入了新的序，重链序。

利用此序，我们可以把一颗树，转化成若干条重链，通过dfs先选重儿子的时间戳得到，最重要的是，同时重链序保持了dfs序的子树结点区间的性质！

怎一个妙字可言。

重链的作用，因为一条重链上的时间戳是连续的，所以如果两个点在同一条重链上，我们就能通过线段树维护。

而又一妙处在于，所有的节点，都能通过上跳，和另一个节点到达同一个重链。

top的深度深的那个节点，向上跳，直到跳到和另一个top相同，

最小路径永远由若干条重链形成，故而在每段旅程，我都可以通过连续区间进行线段树操作。

需要的东西很多，我们分成两次dfs

第一次dfs：

需要：

size【】

fa【】 为了top向上跳的时候

son【】为了在第二次dfs确定重链方向

depth【】 为了比较top，还有就是同一个重链上的两个点的时间戳关系由他体现，便于线段树操作

 1 int size[maxn],fa[maxn],dep[maxn],son[maxn];
 2 void dfs(int pre,int f)
 3 {
 4     fa[pre]=f;
 5     dep[pre]=dep[f]+1;
 6     size[pre]=1;
 7     son[pre]=0;
 8     for(int i=head[pre];i>0;i=edg[i].next)
 9     if(edg[i].to!=f)
10     {
11         dfs(edg[i].to,pre);
12         size[pre]+=size[edg[i].to];
13         if(size[edg[i].to]>size[son[pre]])
14         {
15             son[pre]=edg[i].to;
16         }
17     }
18 }

第二次dfs：

top【】为了上跳

dfn【】

dfni【】

tim 时间戳

 1 void dfs2(int pre,int t)//注意，这个dfs里是x和top的关系，而不是父子关系
 2 {
 3     top[pre]=t;
 4     dfn[pre]=++tim;
 5     dfni[tim]=pre;
 6     if(son[pre]==0)
 7     return;
 8     dfs2(son[pre],t);
 9     for(int i=head[pre];i>0;i=edg[i].next)
10     {
11         if(edg[i].to!=fa[pre]&&edg[i].to!=son[pre])
12         dfs2(edg[i].to,edg[i].to);
13     }
14 }

线段树：

不解释

完整代码如下

  1 #include<iostream>
  2 using namespace std;
  3 int n,m,r,p;
  4 #define maxn 200010
  5 struct star{
  6     int to;
  7     int next;
  8 }edg[maxn];
  9 int cnt=0;
 10 int head[maxn],a[maxn];
 11 void add(int u,int v)
 12 {
 13     edg[++cnt].to=v;
 14     edg[cnt].next=head[u];
 15     head[u]=cnt;
 16 }
 17 int size[maxn],fa[maxn],dep[maxn],son[maxn];
 18 void dfs(int pre,int f)
 19 {
 20     fa[pre]=f;
 21     dep[pre]=dep[f]+1;
 22     size[pre]=1;
 23     son[pre]=0;
 24     for(int i=head[pre];i>0;i=edg[i].next)
 25     if(edg[i].to!=f)
 26     {
 27         dfs(edg[i].to,pre);
 28         size[pre]+=size[edg[i].to];
 29         if(size[edg[i].to]>size[son[pre]])
 30         {
 31             son[pre]=edg[i].to;
 32         }
 33     }
 34 }
 35 int top[maxn],dfn[maxn],dfni[maxn],tim=0;
 36 void dfs2(int pre,int t)//注意，这个dfs里是x和top的关系，而不是父子关系
 37 {
 38     top[pre]=t;
 39     dfn[pre]=++tim;
 40     dfni[tim]=pre;
 41     if(son[pre]==0)
 42     return;
 43     dfs2(son[pre],t);
 44     for(int i=head[pre];i>0;i=edg[i].next)
 45     {
 46         if(edg[i].to!=fa[pre]&&edg[i].to!=son[pre])
 47         dfs2(edg[i].to,edg[i].to);
 48     }
 49 }
 50 int tree[maxn<<2],lazy[maxn<<2];
 51 void pushup(int root)
 52 {
 53     tree[root]=(tree[root*2]+tree[root*2+1])%p;
 54 }
 55 void pushdown(int l,int r,int root)
 56 {
 57     if(lazy[root])
 58     {
 59         int mid=l+(r-l)/2;
 60         tree[root*2]+=lazy[root]*(mid-l+1);
 61         tree[root*2+1]+=lazy[root]*(r-(mid+1)+1);
 62         lazy[root*2]+=lazy[root];
 63         lazy[root*2+1]+=lazy[root];
 64         lazy[root]=0;
 65     }
 66 }
 67 void build(int l,int r,int root)
 68 {
 69     if(l==r)
 70     {
 71         tree[root]=a[dfni[l]]%p;
 72         return;
 73     }
 74     int mid=l+(r-l)/2;
 75     build(l,mid,root*2);
 76     build(mid+1,r,root*2+1);
 77     pushup(root);
 78     return;
 79 }
 80 void update(int fl,int fr,int k,int l,int r,int root)
 81 {
 82     if(fl<=l&&r<=fr)
 83     {
 84         tree[root]+=k*(r-l+1);
 85         tree[root]%=p;
 86         lazy[root]+=k;
 87         return;
 88     }
 89     int mid=l+(r-l)/2;
 90     pushdown(l,r,root);
 91     if(fl<=mid)
 92     update(fl,fr,k,l,mid,root*2);
 93     if(fr>mid)
 94     update(fl,fr,k,mid+1,r,root*2+1);
 95     pushup(root);
 96     return;
 97 }
 98 int query(int fl,int fr,int l,int r,int root)
 99 {
100     if(fl<=l&&r<=fr)
101     {
102         return tree[root];
103     }
104     int mid=l+(r-l)/2;
105     int sum=0;
106     pushdown(l,r,root);
107     if(fl<=mid)
108     sum=(sum+query(fl,fr,l,mid,root*2));
109     if(fr>mid)
110     sum=(sum+query(fl,fr,mid+1,r,root*2+1));
111     return sum%p;
112 }
113 void upchain(int x,int y,int z)
114 {
115     z%=p;
116     while(top[x]!=top[y])
117     {
118         if(dep[top[x]]<dep[top[y]])
119         swap(x,y);
120         update(dfn[top[x]],dfn[x],z,1,n,1);
121         x=fa[top[x]];
122     }
123     if(dep[x]>dep[y])
124     swap(x,y);
125     update(dfn[x],dfn[y],z,1,n,1);
126 }
127 int querychain(int x,int y)
128 {
129     int sum=0;
130     while(top[x]!=top[y])
131     {
132         if(dep[top[x]]<dep[top[y]])
133         swap(x,y);
134         sum+=query(dfn[top[x]],dfn[x],1,n,1);
135         x=fa[top[x]];
136     }
137     if(dep[x]>dep[y])
138     swap(x,y);
139     sum=(sum+query(dfn[x],dfn[y],1,n,1))%p;
140     return sum;
141 }
142 int main(void)
143 {
144     cin>>n>>m>>r>>p;
145     for(int i=1;i<=n;i++)
146     scanf("%d",&a[i]);
147     for(int i=1;i<=n-1;i++)
148     {
149         int u,v;
150         scanf("%d%d",&u,&v);
151         add(u,v);
152         add(v,u);
153     }
154     dfs(r,r);
155     dfs2(r,r);
156     build(1,n,1);
157     for(int i=1;i<=m;i++)
158     {
159         int op,x,y,z;
160         scanf("%d%d",&op,&x);
161         if(op==1)
162         {
163             scanf("%d%d",&y,&z);
164             upchain(x,y,z);
165         }
166         else if(op==2)
167         {
168             scanf("%d",&y);
169             printf("%d\n",querychain(x,y));
170         }
171         else if(op==3)
172         {
173             scanf("%d",&z);
174             update(dfn[x],dfn[x]+size[x]-1,z,1,n,1);
175         }
176         else if(op==4)
177         {
178             printf("%d\n",query(dfn[x],dfn[x]+size[x]-1,1,n,1));
179         }
180     }
181     return 0;
182 }

这篇关于2022.4.10#树链剖分=链式前向星+dfs序+lca思想+线段树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！