正文 

当前位置： 首页 > java > java教程

模板linkcuttree（动态树）

Z-Y-Y-S Z-Y-Y-S     2022-10-09     357

关键词：

题目描述

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。

０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。

１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。

２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。

３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。

输入输出格式

输入格式：

第１行两个整数，分别为Ｎ和Ｍ，代表点数和操作数。

第２行到第Ｎ＋１行，每行一个整数，整数在［１，１０＾９］内，代表每个点的权值。

第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三个整数，分别代表操作类型和操作所需的量。

输出格式：

对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。

输入输出样例

输入样例#1： 复制 
3 3 
1
2
3
1 1 2
0 1 2 
0 1 1
输出样例#1： 复制 
3
1

说明

数据范围： 1≤N,M≤3⋅105

算法原理提供可靠网址：

zyys

这道题用到的技巧：

 

找根：$makeroot(o)$后一直往左走。最后一个节点就是根。（理由：由于$LCT$中$splay$的性质：按深度作为键值）；

 

判断是否之间有边：再$cut$之前，判断根的左儿子是否是另外一个点。（理由：若存在边，则包含这条边的$splay$只有两个节点）。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<queue>
  7 using namespace std;
  8 int xr[300005],ch[300005][2],val[300005],pre[300005],n,m;
  9 bool isrt[300005],rev[300005];
 10 void pushup(int o)
 11 {
 12   if (!o) return;
 13   xr[o]=xr[ch[o][0]]^xr[ch[o][1]]^val[o];
 14 }
 15 void pushdown(int o)
 16 {
 17   if (!o) return;
 18   if (rev[o])
 19     {
 20       int ls=ch[o][0],rs=ch[o][1];
 21       if (ls)
 22     {
 23       rev[ls]^=1;
 24       swap(ch[ls][0],ch[ls][1]);
 25     }
 26       if (rs)
 27     {
 28       rev[rs]^=1;
 29       swap(ch[rs][0],ch[rs][1]);
 30     }
 31       rev[o]=0;
 32     }
 33 }
 34 void push(int o)
 35 {
 36   if (isrt[o]==0)
 37       push(pre[o]);
 38   pushdown(o);
 39 }
 40 void rotate(int o,bool kind)
 41 {
 42   int p=pre[o];
 43   ch[p][!kind]=ch[o][kind];pre[ch[o][kind]]=p;
 44   if (isrt[p]) isrt[o]=1,isrt[p]=0;
 45   else ch[pre[p]][ch[pre[p]][1]==p]=o;
 46   pre[o]=pre[p];
 47   ch[o][kind]=p;pre[p]=o;
 48   pushup(p);pushup(o);
 49 }
 50 void splay(int o)
 51 {
 52   push(o);
 53   while (isrt[o]==0)
 54     {
 55       if (isrt[pre[o]])
 56     rotate(o,ch[pre[o]][0]==o);
 57       else
 58     {
 59       int p=pre[o],kind=ch[pre[p]][0]==p;
 60       if (ch[p][kind]==o)
 61         rotate(o,!kind),rotate(o,kind);
 62       else rotate(p,kind),rotate(o,kind);
 63     }
 64     }
 65 }
 66 void access(int o)
 67 {
 68   int y=0;
 69   while (o)
 70     {
 71       splay(o);
 72       //xr[o]^=xr[ch[o][1]];
 73       isrt[ch[o][1]]=1;isrt[ch[o][1]=y]=0;
 74       pushup(o);
 75       o=pre[y=o];
 76     }
 77 }
 78 void makeroot(int o)
 79 {
 80   access(o);
 81   splay(o);
 82   rev[o]^=1;
 83   swap(ch[o][0],ch[o][1]);
 84 }
 85 int find(int o)
 86 {
 87   makeroot(o);
 88   access(o);splay(o);
 89   while (ch[o][0])
 90     {
 91       o=ch[o][0];
 92     }
 93   return o;
 94 }
 95 void link(int x,int y)
 96 {
 97   makeroot(x);
 98   pre[x]=y;
 99 }
100 void cut(int x,int y)
101 {
102   makeroot(x);access(y);splay(y);
103   if (ch[y][0]!=x) return;
104   pre[x]=0;
105   ch[y][0]=0;
106   isrt[x]=1;
107   pushup(y);
108 }
109 int main()
110 {int i,c,x,y;
111   cin>>n>>m;
112   for (i=1;i<=n;i++)
113     {
114       scanf("%d",&val[i]);
115       xr[i]=val[i];isrt[i]=1;
116     }
117   for (i=1;i<=m;i++)
118     {
119       scanf("%d%d%d",&c,&x,&y);
120       if (c==0)
121     {
122       makeroot(y);
123       access(x);
124       splay(x);
125       printf("%d
",xr[x]);
126     }
127       else if (c==1)
128     {
129       int p=find(x),q=find(y);
130       if (p!=q) link(x,y);
131     }
132       else if (c==2)
133     {
134       cut(x,y);
135     }
136       else if (c==3)
137     {
138       val[x]=y;
139       makeroot(x);
140       pushup(x);
141     }
142     }
143 }

 

luogup3690模板linkcuttree（动态树）

#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<cstdlib>#include<climits>#include<stack>#include<vector>#include<queue& 查看详情

luogu3690模板linkcuttree（动态树）

题目luogu3690硫硼作者想提醒大家，WA了TLE了RE了的，也许只是主函数写错了代码#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstdlib>#include<cstring>usingnamespacestd 查看详情

模板linkcuttree（动态树）

题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的... 查看详情

luogup3690模板linkcuttree（动态树）[lct]

题目背景动态树题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证... 查看详情

数据结构专题-学习笔记：linkcuttree动态树

1.前言LinkCutTree动态树，简称LCT，是一种维护动态森林的数据结构。前置知识：Splay。2.LCT例题：P3690【模板】动态树（LinkCutTree）2.1实链剖分实链剖分也是一种对树的剖分方式，类似于重链剖分和长链剖分，其将一棵树上的边，随... 查看详情

p3690linkcuttree(动态树)

干脆整个LCT模板吧。缺个链上修改和子树操作，链上修改的话join(u,v)然后把vsplay到树根再打个标记就好。至于子树操作...以后有空的话再学(咕咕咕警告)1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintN=1e5+10;5intn,m,a[N],X... 查看详情

p3690模板linkcuttree（动态树）(代码片段)

哇，做梦也没想到我居然能写LCT题意：给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通... 查看详情

刷题洛谷p3690模板linkcuttree（动态树）(代码片段)

题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情

lct(linkcuttree)动态树(代码片段)

模板参考：https://blog.csdn.net/saramanda/article/details/55253627几个知识点：1、LCT中用Splay维护链，这些Splay叫做“辅助树“。辅助树以它上面每个节点的深度为关键字维护，就是辅助树中每个节点左儿子的深度小于当前节点的深度... 查看详情

p3690模板linkcuttree（动态树）(代码片段)

P3690【模板】LinkCutTree（动态树）注意：不要把$fa[x]$和$nrt(x)$混在一起！#include<cstdio>voidswap(int&a,int&b)a^=b^=a^=b;#defineN300005intn,m,s[N],v[N],ch[2][N],fa[N],rev[N];#definelcch[0][x]#definercch[1][x]boolnrt(intx)returnch[0][fa[x]]==x||ch[1][fa[x]]==x;voidu... 查看详情

linkcuttree学习笔记

从这里开始动态树问题和LinkCutTree一些定义access操作换根操作link和cut操作时间复杂度证明LinkCutTree维护链上信息LinkCutTree维护子树信息小结动态树问题和LinkCutTree　　动态树问题是一类要求维护一个有根树森林，支持对树的分割,... 查看详情

linkcuttree动态树小结(代码片段)

动态树有些类似树链剖分+并查集的思想，是用splay维护的lct的根是动态的，"轻重链"也是动态的，所以并没有真正的轻重链动态树的操作核心是把你要把修改/询问/...等等一系列的操作的树链放到一个splay里，然后用splay根据相对... 查看详情

p3690模板linkcuttree（动态树）(代码片段)

LCTLCT即Link-Cut-Tree维护一个森林，支持很多操作，比如：维护链上信息（min，max，sum，xor。。。。。。）换根动态维护联通性维护子树信息概念虚边：连接儿子与父亲，儿子记录父亲，父亲不记录儿子（父不认子）实边：父子互... 查看详情

洛谷p3690模板linkcuttree（lct）(代码片段)

题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：后接两... 查看详情

动态树模板(代码片段)

LinkCutTree:#include<bits/stdc++.h>#defineL(x)T[(x)].son[0]#defineR(x)T[(x)].son[1]#definefa(x)T[(x)].fausingnamespacestd;constintN=300050;intstk[N];intn,m;structTreeintson[2],fa;intval,siz,Xor;booltag;T[N];boolisroot(intx)return(L(fa(x))==x||R(fa(x))==x)==0;voidpushup(intx)T[x].Xor=T[L(x)].Xo... 查看详情

ac日记——模板linkcuttree洛谷p3690

【模板】LinkCutTree 思路：　　LCT模板； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn300005intn,m,val[maxn];inttop,ch[maxn][2],f[maxn],xr[maxn],q[maxn],rev[maxn];inlinevoidin(int&now 查看详情

linkcuttree求最小生成树(代码片段)

对边建点，原图中的边转化为点的点-边的点-点的点于是用LCT维护连通关系，并支持查询最大值位置即可#include<bits/stdc++.h>usingnamespacestd;constintN=300005;intn,m,val[N],t1,t2,t3;namespacelct inttop,q[N],ch[N][2],fa[N],rev[N]; intmx[N]; inlin 查看详情

bzoj-3779重组病毒linkcuttree+线段树+dfs序

3779:重组病毒TimeLimit: 20Sec  MemoryLimit: 512MBSubmit: 224  Solved: 95[Submit][Status][Discuss]Description黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和... 查看详情