正文 

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

linkcuttree

luckyblock luckyblock     2023-03-16     174

关键词： 

//知识点 : LCT 
/*
By:Luckyblock
*/
#include <cstdio>
#include <ctype.h>
#include <algorithm>
#define ls (t[x].son[0])
#define rs (t[x].son[1])
const int kMaxn = 1e5 + 10;
//=============================================================
struct Link_Cut_Tree_Node 
  int son[2], fa;
  int xr, rev;
 t[kMaxn];
int n, m, val[kMaxn], st[kMaxn];
//=============================================================
inline int read() 
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == ‘-‘) f = -1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ ‘0‘);
	return f * w;

void Pushup(int x) 
  t[x].xr = t[ls].xr ^ t[rs].xr ^ val[x];

void PushReverse(int x) 
  std :: swap(ls, rs);
  t[x].rev ^= 1;

void Pushdown(int x) 
  if (! t[x].rev) return ;
  if (ls) PushReverse(ls);
  if (rs) PushReverse(rs);
  t[x].rev = 0;

bool IsNotRoot(int x) 
  return t[t[x].fa].son[0] == x || t[t[x].fa].son[1] == x;

int GetSonNum(int x) 
  return t[t[x].fa].son[1] == x;


void Rotate(int x) 
  int fa = t[x].fa, gfa = t[fa].fa, which_son = GetSonNum(x);
  //注意旋转顺序，在splay中这句可放在最后，但在lct中不可。
  //因为下面的两句改变了结构，无法判断原fa是否为根节点。 
	if (IsNotRoot(fa)) t[gfa].son[t[gfa].son[1] == fa] = x;  
	t[x].fa = gfa;
	
  t[fa].son[which_son] = t[x].son[which_son ^ 1];
	t[t[fa].son[which_son]].fa = fa;
	
	t[x].son[which_son ^ 1] = fa; 
  t[fa].fa = x;
	Pushup(fa);

void Splay(int x) 
  int now = x, cnt = 0;
  st[++ cnt] = now;
  while (IsNotRoot(now)) st[++ cnt] = (now = t[now].fa);
  while (cnt) Pushdown(st[cnt --]);
  
  
  for (int y = t[x].fa; IsNotRoot(x); Rotate(x)) 
    y = t[x].fa;
    if (IsNotRoot(y)) Rotate(GetSonNum(x) == GetSonNum(y) ? y : x);
  
  Pushup(x);

void Access(int x) 
  for (int y = 0; x; y = x, x = t[x].fa) 
    Splay(x), rs = y;
    Pushup(x);
  

void MakeRoot(int x) 
  Access(x);
  Splay(x);
  PushReverse(x);

int FindRoot(int x) 
  Access(x); Splay(x);
  while (ls) Pushdown(x), x = ls;
  Splay(x);
  return x;

void Split(int x, int y) 
  MakeRoot(x);
  Access(y);
  Splay(y);

void Cut(int x, int y) 
  MakeRoot(x);
  if(FindRoot(y) != x || t[y].fa != x || t[y].son[0]) return ;
  t[y].fa = t[x].son[1] = 0;
  Pushup(x);

void Link(int x, int y) 
  MakeRoot(x);
  if(FindRoot(y) != x) t[x].fa = y;

//=============================================================
int main() 
  n = read(), m = read();
  for (int i = 1; i <= n; ++ i) 
    t[i].xr = val[i] = read(); 
  
  for (int i = 1; i <= m; ++ i) 
    int opt = read(), x = read(), y = read();
    if (opt == 0) 
      Split(x, y);
      printf("%d
", t[y].xr);
    
    if (opt == 1) Link(x, y);
    if (opt == 2) Cut(x, y);
    if (opt == 3) 
      Splay(x);
      val[x] = y;
    
  
	return 0;

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

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

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 查看详情

p3690linkcuttree(动态树)

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

[]linkcuttree

坑了好久，本来打算就这样弃着，最近又被神秘力量驱使来学这个东西，过程很痛苦但最终还是知道它到底是啥了它可以用来对森林进行各种操作，为了快速地实现各种操作，我们要像树剖一样把整个森林剖成许多条链，每条链... 查看详情

luogu3690模板linkcuttree（动态树）

参考there和there#include<iostream>#include<cstdio>usingnamespacestd;intn,m,val[300005],ch[300005][2],sum[300005],fa[300005],uu,vv,opt;intrev[300005];voidpushDown(intx)if(rev[x])swap(ch[x][0 查看详情

luogup3690模板linkcuttree（动态树）

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

linkcuttree（无图慎入）(代码片段)

类似树链剖分（其实直接记住就可以了），提前放代码1#include<cstdio>2#include<cstdlib>3#include<iostream>4#include<algorithm>5#include<cstring>6#include<climits>7#include<cmath>8#define 查看详情

luogu3690模板linkcuttree（动态树）

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

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 查看详情

ural题目1553.cavesandtunnels（linkcuttree改动点权，求两点之间最大）

1553.CavesandTunnelsTimelimit:3.0secondMemorylimit:64MBAfterlandingonMarssurface,scientistsfoundastrangesystemofcavesconnectedbytunnels.Sotheybegantoresearchitusingremotecontrolledrobots.Itwasfoundout 查看详情

bzoj-2555substring后缀自动机+linkcuttree

2555:SubStringTimeLimit: 30Sec  MemoryLimit: 512MBSubmit: 1936  Solved: 551[Submit][Status][Discuss]Description    懒得写背景了，给你一个字符串init，要求你支持两 查看详情

模板linkcuttree（动态树）

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

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

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

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

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

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

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

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

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

linkcuttree

//知识点:LCT/*By:Luckyblock*/#include<cstdio>#include<ctype.h>#include<algorithm>#definels(t[x].son[0])#definers(t[x].son[1])constintkMaxn=1e5+10;//=============================================================structLink_Cut_Tree_Nodeintson[2],fa;intxr,rev;t[kMaxn];intn,m,val[kMa... 查看详情

洛谷3690：模板linkcuttree——题解(代码片段)

https://www.luogu.org/problemnew/show/P3690给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：... 查看详情