CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » legal_string » 树链剖分_lgwza
2020-2021:teams:legal_string:树链剖分_lgwza

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

后一修订版 		前一修订版
2020-2021:teams:legal_string:树链剖分_lgwza [2020/07/07 15:15]
lgwza 创建 		2020-2021:teams:legal_string:树链剖分_lgwza [2020/08/04 22:21] (当前版本)
lgwza [例题]
行 71: 行 71:
 \end{array}\end{array} \end{array}\end{array}
 $$ 以下为代码实现。 $$ 以下为代码实现。
 +
 +我们先给出一些定义：
 +
 +  * $fa(x)$ 表示结点 $x$ 在树上的父亲。
 +  * $dep(x)$ 表示结点 $x$ 在树上的深度。
 +  * $siz(x)$ 表示结点 $x$ 的子树的结点个数。
 +  * $son(x)$ 表示结点 $x$ 的**重儿子**。
 +  * $top(x)$ 表示结点 $x$ 所在**重链**的顶部结点（深度最小）。
 +  * $dfn(x)$ 表示结点 $x$ 的**DFS序**，也是其在线段树中的编号。
 +  * $rnk(x)$ 表示 DFS 序所对应的结点编号，有 $rnk(dfn(x))=x$ 。
 +
 +我们进行两遍 DFS 预处理出这些值，其中第一次 DFS 求出 $fa(x),​dep(x),​siz(x),​son(x)$，第二次 DFS 求出 $top(x),​dfn(x),​rnk(x)$。
 +
 +<code cpp>
 +void dfs1(int o){
 +    son[o]=-1;
 +    siz[o]=1;
 +    for(int j=h[o];​j;​j=nxt[j]){
 +        if(!dep[p[j]]){
 +            dep[p[j]]=dep[o]+1;​
 +            fa[p[j]]=o;
 +            dfs1(p[j]);
 +            siz[o]+=siz[p[j]];​
 +            if(son[o]==-1||siz[p[j]]>​siz[son[o]]) son[o]=p[j];​
 +        }
 +    }
 +}
 +void dfs2(int o,int t){
 +    top[o]=t;
 +    cnt++;
 +    dfn[o]=cnt;
 +    rnk[cnt]=o;
 +    if(son[o]==-1) return;
 +    dfs2(son[o],​t);//​ 优先对重儿子进行 DFS ，可以保证同一条重链上的点 DFS 序连续
 +    for(int j=h[o];​j;​j=nxt[j]){
 +        if(p[j]!=son[o]&&​p[j]!=fa[o]) dfs2(p[j],​p[j]);​
 +    }
 +}
 +</​code>​
 +===== 重链剖分的性质 =====
 +
 +**树上每个结点都属于且仅属于一条重链**。
 +
 +重链开头的结点不一定是重子结点（因为重边是对于每一个结点都有定义的）。
 +
 +所有的重链将整棵树**完全剖分**。
 +
 +在剖分时**优先遍历重儿子**，最后重链的 DFS 序就会是连续的。
 +
 +在剖分时**重边优先遍历**，最后树的 DFN 序上，重链内的 DFN 序是连续的。按 DFN 排序后的序列即为剖分后的链。
 +
 +一棵子树内的 DFN 序是连续的。
 +
 +可以发现，当我们向下经过一条轻边时，所在子树的大小至少会除以二。
 +
 +因此，对于树上的任意一条路径，把它拆分成从 LCA 分别向两边往下走，分别最多走 $O(\log n)$次，因此，树上的每条路径都可以被拆分成不超过 $O(\log n)$条重链。
 +
 +===== 常见应用 =====
 +
 +==== 路径上维护 ====
 +
 +用树链剖分求树上两点路径权值和，伪代码如下： $$
 +\begin{array}{l}\text{TREE-PATH-SUM }(u,v)\\
 +\begin{array}{ll}
 +1 & tot\gets 0 \\
 +2 & \textbf{while }u.top\text{ is not }v.top\\
 +3 & \qquad\textbf{if }u.top.deep<​v.top.deep\\
 +4& \qquad\qquad\text{SWAP}(u,​v)\\
 +5 & \qquad tot\gets tot+\text{sum of values between }u\text{ and }u.top\\
 +6 & \qquad u \gets u.top.father\\
 +7 & tot\gets tot +\text{sum of values between }u\text{ and }v\\
 +8 & \textbf{return }tot
 +\end{array}\end{array}
 +$$ 链上的 DFS 序是连续的，可以使用线段树、树状数组维护。
 +
 +每次选择深度较大的链往上跳，直到两点在同一条链上。
 +
 +同样的跳链结构适用于维护、统计路径上的其他信息。
 +
 +==== 子树维护 ====
 +
 +有时会要求维护子树上的信息，譬如将以 $x$ 为根的子树的所有结点的权值增加 $v$。
 +
 +在 DFS 搜索的时候，子树中的结点的 DFS 序是连续的。
 +
 +每一个结点记录 bottom 表示所在子树连续区间末端的结点。
 +
 +这样就把子树信息转化为连续的一段区间信息。
 +
 +==== 求最近公共祖先 ====
 +
 +不断向上跳重链，当跳到同一条重链上时，深度较小的结点即为 LCA。
 +
 +向上跳重链时需要先跳所在重链顶端深度较大的那个。
 +
 +参考代码：
 +
 +<code cpp>
 +int lca(int u,int v){
 +    while(top[u]!=top[v]){
 +        if(dep[top[u]]>​dep[top[v]])
 +            u=fa[top[u]];​
 +        else
 +            v=fa[top[v]];​
 +    }
 +    return dep[u]>​dep[v]?​v:​u;​
 +}
 +</​code>​
 +
 +===== 例题 =====
 +[[https://​www.luogu.com.cn/​problem/​P3384|P3384 【模板】轻重链剖分]]
 +
 +参考代码：
 +
 +<​hidden>​
 +<code cpp>
 +#​include<​bits/​stdc++.h>​
 +using namespace std;
 +const int N=1e5+5;
 +typedef long long ll;
 +
 +int n,​m,​root,​mod;​
 +int cnt,​head[N],​nxt[N<<​1],​to[N<<​1],​w[N],​nw[N];​
 +int tr[N<<​2],​add[N<<​2];​
 +int hson[N],​dfn[N],​fa[N],​tot,​dep[N],​siz[N],​top[N],​rk[N];​
 +void addedge(int u,int v){
 + nxt[++cnt]=head[u];​
 + head[u]=cnt;​
 + to[cnt]=v;
 +}
 +// segment tree
 +inline int ls(int o){
 + return o<<1;
 +}
 +inline int rs(int o){
 + return o<<​1|1;​
 +}
 +void push_up(int o){
 + tr[o]=(tr[ls(o)]+tr[rs(o)])%mod;​
 +}
 +void build(int o,int l,int r){
 + if(l==r){
 + tr[o]=nw[l]%mod;​
 + return;
 + }
 + int mid=l+r>>​1;​
 + build(ls(o),​l,​mid);​
 + build(rs(o),​mid+1,​r);​
 + push_up(o);​
 +}
 +void f(int o,int l,int r,int k){
 + add[o]=(add[o]+k);​
 + tr[o]=(tr[o]+(r-l+1)*k)%mod;​
 +}
 +void push_down(int o,int l,int r){
 + int mid=l+r>>​1;​
 + f(ls(o),​l,​mid,​add[o]);​
 + f(rs(o),​mid+1,​r,​add[o]);​
 + add[o]=0;
 +}
 +void xg(int o,int nl,int nr,int l,int r,int k){
 + if(nl<​=l&&​r<​=nr){
 + add[o]=(add[o]+k)%mod;​
 + tr[o]=(tr[o]+(r-l+1)*k)%mod;​
 + return;
 + }
 + push_down(o,​l,​r);​
 + int mid=l+r>>​1;​
 + if(nl<​=mid) xg(ls(o),​nl,​nr,​l,​mid,​k);​
 + if(nr>​mid) xg(rs(o),​nl,​nr,​mid+1,​r,​k);​
 + push_up(o);​
 +}
 +int cx(int o,int nl,int nr,int l,int r){
 + if(nl<​=l&&​r<​=nr) return tr[o]%mod;
 + push_down(o,​l,​r);​
 + int ret=0;
 + int mid=l+r>>​1;​
 + if(nl<​=mid) ret+=cx(ls(o),​nl,​nr,​l,​mid);​
 + if(nr>​mid) ret+=cx(rs(o),​nl,​nr,​mid+1,​r);​
 + return ret%mod;
 +}
 +// original tree
 +int cxRange(int x,int y){
 + int ans=0;
 + while(top[x]!=top[y]){
 + if(dep[top[x]]<​dep[top[y]]) swap(x,y);
 + ans+=cx(1,​dfn[top[x]],​dfn[x],​1,​n);​
 + ans%=mod;
 + x=fa[top[x]];​
 + }
 + if(dep[x]>​dep[y]) swap(x,y);
 + ans+=cx(1,​dfn[x],​dfn[y],​1,​n);​
 + ans%=mod;
 + return ans;
 +}
 +void xgRange(int x,int y,int k){
 + k%=mod;
 + while(top[x]!=top[y]){
 + if(dep[top[x]]<​dep[top[y]]) swap(x,y);
 + xg(1,​dfn[top[x]],​dfn[x],​1,​n,​k);​
 + x=fa[top[x]];​
 + }
 + if(dep[x]>​dep[y]) swap(x,y);
 + xg(1,​dfn[x],​dfn[y],​1,​n,​k);​
 +}
 +int cxSon(int x){
 + return cx(1,​dfn[x],​dfn[x]+siz[x]-1,​1,​n);​
 +}
 +void xgSon(int x,int k){
 + xg(1,​dfn[x],​dfn[x]+siz[x]-1,​1,​n,​k);​
 +}
 +// dfs
 +void dfs1(int u,int f,int deep){
 + dep[u]=deep;​
 + siz[u]=1;
 + fa[u]=f;
 + for(int i=head[u];​i;​i=nxt[i]){
 + int v=to[i];
 + if(v==fa[u]) continue;
 + dfs1(v,​u,​deep+1);​
 + siz[u]+=siz[v];​
 + if(hson[u]==0||siz[hson[u]]<​siz[v]) hson[u]=v;
 + }
 +}
 +void dfs2(int u,int t){
 + top[u]=t;
 + dfn[u]=++tot;​
 + nw[tot]=w[u];​
 + rk[tot]=u;
 + if(!hson[u]) return;
 + dfs2(hson[u],​t);​
 + for(int i=head[u];​i;​i=nxt[i]){
 + int v=to[i];
 + if(v==fa[u]||v==hson[u]) continue;
 + dfs2(v,​v);​
 + }
 +}
 +int main(){
 + scanf("​%d %d %d %d",&​n,&​m,&​root,&​mod);​
 + for(int i=1;​i<​=n;​i++) scanf("​%d",&​w[i]);​
 + for(int i=1;​i<​=n-1;​i++){
 + int x,y;
 + scanf("​%d %d",&​x,&​y);​
 + addedge(x,​y);​
 + addedge(y,​x);​
 + }
 + dfs1(root,​0,​1);​
 + dfs2(root,​root);​
 + build(1,​1,​n);​
 +//​ printf("​fadfa\n"​);​
 + while(m--){
 + int op;
 + scanf("​%d",&​op);​
 + if(op==1){
 + int x,y;
 + int k;
 + scanf("​%d %d %d",&​x,&​y,&​k);​
 + k%=mod;
 + xgRange(x,​y,​k);​
 + }
 + else if(op==2){
 + int x,y;
 + scanf("​%d %d",&​x,&​y);​
 + printf("​%d\n",​cxRange(x,​y));​
 + }
 + else if(op==3){
 + int x;
 + int k;
 + scanf("​%d %d",&​x,&​k);​
 + k%=mod;
 + xgSon(x,​k);​
 + }
 + else if(op==4){
 + int x;
 + scanf("​%d",&​x);​
 + printf("​%d\n",​cxSon(x));​
 + }
 + }
 +
 + return 0;
 +}
 +</​code>​
 +</​hidden>​
 +
 +===== 参考资料 =====
 +[[https://​oi-wiki.org/​graph/​hld/​|OI Wiki]]
2020-2021/teams/legal_string/树链剖分_lgwza.1594106140.txt.gz · 最后更改: 2020/07/07 15:15 由 lgwza

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3