[关闭]
@exut 2024-11-14T02:46:57.000000Z 字数 5271 阅读 116

LCT的114514种处理寄巧

DS

本文针对的是会板子，稍微对LCT有一点点理解但是不会各种典型处理的人，比如我自己（bushi）

作者学到哪就写到哪，如果停止更新说明作者┏┛墓┗┓...(((m-__-)m

边权怎么办

众所周知的是树剖使用的是把边权放在深度较深的点上，查询时挖掉LCA的方式来实现边权转点权

但是，令人遗憾的是，LCT的动态结构不太支持这么搞

一种常见的处理方式（可能有更为厉害的处理方式，但是我并不会）

假如两个点在原树存在一条边，那么我们在他们俩之间建立一个点储存边的信息然后向两边连边

我们可以令第 条边的边点编号为 ，然后pushup和pushdown会有点难写

例子：P1505 [国家集训队] 旅游

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=4e5+5;
  4. const int inf=1e9;
  5. int val[N];
  6. int n,m;
  7. struct LCT{
  8.     int fa[N],ch[N][2],rev[N],tag[N];
  9.     int sum[N],mx[N],mi[N];
  10.     bool isd(int x){return ch[fa[x]][2]==x;}
  11.     bool isroot(int x){return (ch[fa[x]][0]!=x and ch[fa[x]][3]!=x);}
  12.     void pushup(int x){
  13.         if(x>n) sum[x]=mx[x]=mi[x]=val[x];
  14.         else sum[x]=0,mx[x]=-inf,mi[x]=inf;
  15.         sum[x]+=sum[ch[x][0]]+sum[ch[x][4]];
  16.         if(ch[x][0]){
  17.             mx[x]=max(mx[x],mx[ch[x][0]]);
  18.             mi[x]=min(mi[x],mi[ch[x][0]]);
  19.         }
  20.         if(ch[x][5]){
  21.             mx[x]=max(mx[x],mx[ch[x][6]]);
  22.             mi[x]=min(mi[x],mi[ch[x][7]]);
  23.         }
  24.     }
  25.     void pushdown(int x){
  26.         if(rev[x]){
  27.             rev[x]=0;
  28.             swap(ch[x][0],ch[x][8]);
  29.             rev[ch[x][0]]^=1;
  30.             rev[ch[x][9]]^=1;
  31.         }
  32.         if(tag[x]){
  33.             tag[x]=0;
  34.             swap(mx[ch[x][0]],mi[ch[x][0]]);
  35.             val[ch[x][0]]=-val[ch[x][0]];
  36.             mx[ch[x][0]]=-mx[ch[x][0]];
  37.             mi[ch[x][0]]=-mi[ch[x][0]];
  38.             sum[ch[x][0]]=-sum[ch[x][0]];
  39.             tag[ch[x][0]]^=1;
  40.             swap(mx[ch[x][10]],mi[ch[x][11]]);
  41.             val[ch[x][12]]=-val[ch[x][13]];
  42.             mx[ch[x][14]]=-mx[ch[x][15]];
  43.             mi[ch[x][16]]=-mi[ch[x][17]];
  44.             sum[ch[x][18]]=-sum[ch[x][19]];
  45.             tag[ch[x][20]]^=1;
  46.         }
  47.     }
  48.     void rotate(int x){
  49.         int y=fa[x],z=fa[y];
  50.         int k=isd(x);
  51.         if(!isroot(y)) ch[z][isd(y)]=x;
  52.         fa[x]=z;
  53.         ch[y][k]=ch[x][k^1];
  54.         fa[ch[x][k^1]]=y;
  55.         fa[y]=x;
  56.         ch[x][k^1]=y;
  57.         pushup(y),pushup(x);
  58.     }
  59.     stack<int,vector<int> > stk;
  60.     void splay(int x){
  61.         stk.push(x);
  62.         for(int i=x;!isroot(i);i=fa[i]) stk.push(fa[i]);
  63.         while(!stk.empty()) pushdown(stk.top()),stk.pop();
  64.         while(!isroot(x)){
  65.             int y=fa[x];
  66.             if(!isroot(y)) (isd(x)==isd(y))?rotate(y):rotate(x);
  67.             rotate(x);
  68.         }
  69.     }
  70.     void access(int x){
  71.         for(int t=0;x;t=x,x=fa[x])
  72.             splay(x),ch[x][21]=t,pushup(x);
  73.     }
  74.     void makeroot(int x){
  75.         access(x);
  76.         splay(x);
  77.         rev[x]^=1;
  78.     }
  79.     int findroot(int x){
  80.         access(x);
  81.         splay(x);
  82.         while(ch[x][0]) x=ch[x][0];
  83.         splay(x);
  84.         return x;
  85.     }
  86.     void split(int x,int y){
  87.         makeroot(x);
  88.         access(y);
  89.         splay(y);
  90.     }
  91.     void link(int x,int y){
  92.         makeroot(x);
  93.         if(findroot(y)!=x) fa[x]=y;
  94.     }
  95. }lct;
  98. int main(){
  99.     ios::sync_with_stdio(0);
  100.     cin.tie(0),cout.tie(0);
  101.     cin>>n;
  102.     for(int i=1;i<n;i++){
  103.         int u,v;
  104.         cin>>u>>v;
  105.         u++,v++;
  106.         cin>>val[i+n];
  107.         lct.link(u,i+n);
  108.         lct.link(v,i+n);
  109.     }
  110.     cin>>m; 
  111.     while(m--){
  112.         string opt;
  113.         int x,y;
  114.         cin>>opt>>x>>y;
  115.         if(opt!="C") x++,y++;
  116.         if(opt=="C"){
  117.             lct.splay(x+n);
  118.             val[x+n]=y;
  119.             lct.pushup(x+n);
  120.         }else if(opt=="N"){
  121.             lct.split(x,y);
  122.             lct.tag[y]^=1; 
  123.         }else if(opt=="SUM"){
  124.             lct.split(x,y);
  125.             cout<<lct.sum[y]<<"\n";
  126.         }else if(opt=="MAX"){
  127.             lct.split(x,y);
  128.             cout<<lct.mx[y]<<"\n";
  129.         }else if(opt=="MIN"){
  130.             lct.split(x,y);
  131.             cout<<lct.mi[y]<<"\n";
  132.         }
  133.     }
  134. }

维护生成树

以维护MST为例

P4172 [WC2006] 水管局长

一个典型的转化是瓶颈路最小就是最小生成树上链最大值

然后这道题的题意就转化成了LCT上维护MST

首先把删边逆序转化成加边，那么考虑在当前最小生成树的基础上加一条边的变化：多了一个环

如果加进来的边比当前环的最大值还要大，这个边毫无意义不需要加入

否则删掉最大边，并link上当前边即可

实现有点困难，细节有点多

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int N=2e5+5;
  5. const int inf=1e9;
  6. struct edge{
  7.     int u,v,w;
  8. };
  9. vector<edge> e;
  10. struct que{
  11.     int u,v;
  12. };
  13. que ctt[N];
  14. que Q[N];
  15. int n,m;
  16. int fa[N],ch[N][2],val[N],mx[N],mpos[N],rev[N];
  17. bool isd(int x){
  18.     return ch[fa[x]][1]==x;
  19. }
  20. bool isroot(int x){
  21.     return ch[fa[x]][0]!=x and ch[fa[x]][1]!=x;
  22. }
  23. void pushup(int x){
  24.     if(x>n) mx[x]=val[x],mpos[x]=x;
  25.     else mx[x]=-inf,mpos[x]=-1;
  26.     if(ch[x][0]){
  27.         if(mpos[ch[x][0]]!=-1 and (mpos[x]==-1 or mx[ch[x][0]]>mx[x])){
  28.             mpos[x]=mpos[ch[x][0]];
  29.             mx[x]=mx[ch[x][0]];
  30.         }
  31.     }
  32.     if(ch[x][1]){
  33.         if(mpos[ch[x][1]]!=-1 and (mpos[x]==-1 or mx[ch[x][1]]>mx[x])){
  34.             mpos[x]=mpos[ch[x][1]];
  35.             mx[x]=mx[ch[x][1]];
  36.         }
  37.     }
  38. }
  39. void pushdown(int x){
  40.     if(rev[x]){
  41.         rev[x]=0;
  42.         swap(ch[x][0],ch[x][1]);
  43.         if(ch[x][0]) rev[ch[x][0]]^=1;
  44.         if(ch[x][1]) rev[ch[x][1]]^=1;
  45.     }
  46. }
  47. void rotate(int x){
  48.     int y=fa[x],z=fa[y];
  49.     int k=isd(x);
  50.     fa[ch[x][k^1]]=y;
  51.     ch[y][k]=ch[x][k^1];
  52.     if(!isroot(y)) ch[z][isd(y)]=x;
  53.     fa[x]=z;
  54.     fa[y]=x;
  55.     ch[x][k^1]=y;
  56.     pushup(y),pushup(x);
  57. }
  58. stack<int,vector<int> > stk;
  59. void splay(int x){
  60.     stk.push(x);
  61.     for(int i=x;!isroot(i);i=fa[i]) stk.push(fa[i]);
  62.     while(!stk.empty()) pushdown(stk.top()),stk.pop();
  63.     while(!isroot(x)){
  64.         int y=fa[x];
  65.         if(!isroot(y)) (isd(x)==isd(y))?rotate(y):rotate(x);
  66.         rotate(x);
  67.     }
  68. }
  69. void access(int x){
  70.     for(int t=0;x;t=x,x=fa[x]){
  71.         splay(x),ch[x][1]=t,pushup(x);
  72.     }
  73. }
  74. void makeroot(int x){
  75.     access(x);
  76.     splay(x);
  77.     rev[x]^=1;
  78. }
  79. int findroot(int x){
  80.     access(x);
  81.     splay(x);
  82.     while(ch[x][0]) x=ch[x][0];
  83.     splay(x);
  84.     return x;
  85. }
  86. void split(int x,int y){
  87.     makeroot(x);
  88.     access(y);
  89.     splay(y);
  90. }
  91. void link(int x,int y){
  92.     makeroot(x);
  93.     if(findroot(y)!=x) fa[x]=y;
  94. }
  95. void cut(int x,int y){
  96.     makeroot(x);
  97.     if(findroot(y)==x and fa[y]==x and !ch[y][0]) 
  98.         fa[y]=ch[x][1]=0,pushup(x);
  99. }
  100. int q;
  101. int f[1005][1005];
  102. edge ct[N];
  103. bool cmp(edge x,edge y){
  104.     return x.w<y.w;
  105. }
  106. int ufs[N];
  107. int find(int x){
  108.     return x==ufs[x]?x:ufs[x]=find(ufs[x]);
  109. }
  110. int idx;
  111. int main(){
  112.     ios::sync_with_stdio(0);
  113.     cin.tie(0),cout.tie(0);
  114.     cin>>n>>m>>q;
  115.     for(int i=1;i<=m;i++){
  116.         int u,v,w;
  117.         cin>>u>>v>>w;
  118.         f[u][v]=f[v][u]=w;
  119.         // cin>>e[i].u>>e[i].v>>e[i].w;
  120.     }
  121.     for(int i=1;i<=q;i++){
  122.         int k,x,y;
  123.         cin>>k>>x>>y;
  124.         if(k==1){
  125.             Q[i]={x,y};
  126.         }else{
  127.             ct[i]={x,y,f[x][y]};
  128.             f[x][y]=0;
  129.             f[y][x]=0;
  130.         }
  131.     }
  132.     for(int i=1;i<=n;i++){
  133.         for(int j=i+1;j<=n;j++){
  134.             if(f[i][j]) e.push_back({i,j,f[i][j]});
  135.         }
  136.     }
  137.     idx=n;
  138.     sort(e.begin(),e.end(),cmp);
  139.     for(int i=1;i<=n;i++){
  140.         ufs[i]=i;
  141.     }
  142.     for(auto L:e) {
  143.         int u=L.u,v=L.v,w=L.w;
  144.         if(find(u)==find(v)) continue;
  145.         ufs[find(u)]=find(v);
  146.         idx++;
  147.         val[idx]=w;
  148.         ctt[idx]={u,v};
  149.         link(u,idx);
  150.         link(v,idx);
  151.     }
  152.     stack<int,vector<int> > ans;
  153.     for(int i=q;i;i--){
  154.         if(ct[i].u!=0){
  155.             int u=ct[i].u,v=ct[i].v,w=ct[i].w;
  156.             split(u,v);
  157.             if(w>mx[v]) continue;
  158.             int gg=mpos[v];
  159.             ++idx;
  160.             val[idx]=w;
  161.             ctt[idx].u=u,ctt[idx].v=v;
  162.             cut(u,gg),cut(v,gg);
  163.             link(u,idx),link(v,idx);
  164.         }else{
  165.             int u=Q[i].u,v=Q[i].v;
  166.             split(u,v);
  167.             ans.push(mx[v]);
  168.         }
  169.     }
  170.     while(!ans.empty()){
  171.         cout<<ans.top()<<"\n";
  172.         ans.pop();
  173.     }
  174. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注