主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解:P3690 【模板】动态树(LCT)
最后更新于 2025-07-31 11:10:15
作者
dmh2012901
分类
题解
题解
P3690
复制 Markdown
查看原文
删除文章
更新内容
看完题明显是LCT~~从题目知道的~~ 同时是个动态树问题~~废话~~ ### 什么是动态树问题 维护一个 森林,支持删除某条边,加入某条边,并保证加边,删边之后仍是森林。我们要维护这个森林的一些信息。 一般的操作有两点连通性,两点路径权值和,连接两点和切断某条边、修改信息等。 ### 什么是LCT LCT的核心思想基于实链剖分与Splay树的结合。我们可以简单的把 LCT 理解成用一些 Splay 来维护动态的树链剖分,以期实现动态树上的区间操作。对于每条实链,我们建一个 Splay 来维护整个链区间的信息。 ### 核心概念与原理 #### 实链剖分 将树边划分为实边(重边)和虚边(轻边),每条实边构成的链称为实链。 **辅助树**(Splay树):每条实链用一棵 Splay 树维护,Splay 的中序遍历对应原树中从浅到深的路径。 **虚实边动态转换**:LCT 通过动态调整虚实边,实现树结构的灵活重组。 #### 关键操作 $access(x)$ :打通从节点 $x$ 到根节点的实链,是 LCT 的核心操作 $makeroot(x)$ :将 x 设为原树的根。 $findroot(x)$ :找 x 所在原树的根。 $link(x, y)$ :连接两棵树的边(需确保 $x$ , $y$ 不连通)。 $cut(x, y)$ : 删除边 $(x, y)$ 。 $split(x, y)$ : 分离 $x$ 到 $y$ 的路径。 ### 代码 :::warning[补药复制]{open} ::: ``` #include<bits/stdc++.h> #define int long long #define isrt(x) (ch[f[x]][0]!=x&&ch[f[x]][1]!=x) #define get(x) (ch[f[x]][1]==x) #define st first #define nd second using namespace std; int n,m,ch[100055][2],sz[100055],tag[100055],f[100055],sum[100055],v[100055],laz[100055]; void pushup(int rt){ sz[rt]=sz[ch[rt][0]]+sz[ch[rt][1]]+1; sum[rt]=sum[ch[rt][0]]^sum[ch[rt][1]]^v[rt]; } void pushr(int rt){ swap(ch[rt][0],ch[rt][1]);tag[rt]^=1;} void pushdown(int rt){ if(tag[rt]){ if(ch[rt][0]) pushr(ch[rt][0]); if(ch[rt][1]) pushr(ch[rt][1]); tag[rt]=0; } } void rotate(int rt){ int y=f[rt],z=f[y],k=get(rt); if(!isrt(y)) ch[z][ch[z][1]==y]=rt; ch[y][k]=ch[rt][!k]; f[ch[rt][!k]]=y; ch[rt][!k]=y; f[y]=rt; f[rt]=z; pushup(y); pushup(rt); } void update(int rt){ if(!isrt(rt)) update(f[rt]); pushdown(rt); } void splay(int rt){ update(rt); for(int fa;fa=f[rt],!isrt(rt);rotate(rt)){ if(!isrt(fa)) rotate(get(fa)==get(rt)?fa:rt); } pushup(rt); } int access(int rt){ int p; for(p=0;rt;p=rt,rt=f[rt]){ splay(rt); ch[rt][1]=p; pushup(rt); } return p; } void makeroot(int rt){ rt=access(rt); splay(rt); swap(ch[rt][0],ch[rt][1]); tag[rt]^=1; } int find(int rt){ access(rt); splay(rt); pushdown(rt); while(ch[rt][0]) rt=ch[rt][0],pushdown(rt); splay(rt); return rt; } void link(int rt,int x){ if(find(rt)==find(x)) return; makeroot(rt); f[rt]=x; } void cut(int x,int y){ makeroot(x); access(y); splay(y); if(ch[y][0]==x&&!ch[x][1]&&ch[x][0]){ ch[y][0]=f[x]=0; pushup(y); } } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>v[i]; sz[i]=1; sum[i]=v[i]; } while(m--){ int k,x,y; cin>>k>>x>>y; if(k==0){ makeroot(x); access(y); splay(y); cout<<sum[y]<<endl; } else if(k==1) link(x,y); else if(k==2) cut(x,y); else{ splay(x); v[x]=y; pushup(x); } } return 0; } ```
正在渲染内容...
点赞
1
收藏
0