luogu P3690 【模板】Link Cut Tree （动态树）

嘟嘟嘟

LCT竟然看了整整一天，但好歹是看懂了。

教程这里不写，强烈推荐 闪狐大佬的博客。

但是还是有几句想说的。

1.尽管LCT和splay很像，但是有一些细节还是不一样的。首先是rotate，我们习惯性的令\(y\)为\(x\)的父亲，\(z\)为\(y\)的父亲。这时候一定要判断\(y\)是否为当前splay（这是一个名词）的根，是的话在从\(z\)连向\(x\)。

平时之所以不用判断，是因为当\(y\)为根的时候\(z\)自然是\(0\)。而此时\(z\)是另一棵splay的一个节点，自然不能连边。

但这时候\(x\)的父亲还是要连向\(z\)的，代表一条虚边。

2.splay操作也是有区别的。首先要将这条路径上的点从上到下pushdown一遍，然后再正常的旋到根。为啥咧？想一下普通的splay，如果我们要找树上的结点\(u\)，一定是从根节点往下一路找到的，所以该下传的都下传了，splay的时候自然不用。但是在lct中，是可以直接找到该节点的，所以还得把根节点到这个节点的路径都pushdown一遍。

3.对于实边和虚边，闪狐大佬讲的很好：虚边是认父不认子。也就是说，一条虚边只能连一条从儿子到父亲的单向边，如果从父亲再连一条边，就变成实边了。

4.access操作跟准确来说是把\(x\)所在splay和原树根节点所在splay连接在一起。而不一定要直接把\(x\)和树根相连。

而且连完后，这棵splay里只有\(x\)到树根的路径上的点，只有这样，才能维护树上的链。

5.一棵splay向另一棵splay连边。虽然是一棵splay的根节点向另一棵splay连边，但规则是splay中深度最小的点向另一棵splay中原树上的点连边，也就是说原树上的边是虚边的时候，虚边的两端和原树边的两端不一定一样。

大概就是这些，剩下的可以看代码及注释

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define rg register

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 3e5 + 5;

inline ll read()

{

  ll ans = 0;

  char ch = getchar(), last = ' ';

  while(!isdigit(ch)) last = ch, ch = getchar();

  while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  if(last == '-') ans = -ans;

  return ans;

}

inline void write(ll x)

{

  if(x < 0) x = -x, putchar('-');

  if(x >= 10) write(x / 10);

  putchar(x % 10 + '0');

}

int n, m;

struct Tree

{

  int ch[2], fa;

  int val, sum, rev;

}t[maxn];

void _PrintTr(int now)

{

  if(!now) return;

  printf("-->now:%d val:%d sum:%d ls:%d rs%d\n", now, t[now].val, t[now].sum, t[now].ch[0], t[now].ch[1]);

  _PrintTr(t[now].ch[0]); _PrintTr(t[now].ch[1]);

}

void pushup(int now)  //别跟线段树搞混,一定要算上自己

{

  t[now].sum = t[t[now].ch[0]].sum ^ t[t[now].ch[1]].sum ^ t[now].val;

}

void change(int now)

{

  swap(t[now].ch[0], t[now].ch[1]); t[now].rev ^= 1;

}

void pushdown(int now)

{

  if(t[now].rev)

    {

      if(t[now].ch[0]) change(t[now].ch[0]);

      if(t[now].ch[1]) change(t[now].ch[1]);

      t[now].rev = 0;

    }

}

bool n_root(int now)  //根节点的父亲不一定是0了,所以必须要判断一下,也就是这条边是不是虚边

{

  return t[t[now].fa].ch[0] == now || t[t[now].fa].ch[1] == now;

}

void rotate(int x)  //一定要有这个判断条件,因为当y是根的时候,z就不应该向y连边,但父亲可以指向z,代表虚边

{

  int y = t[x].fa, z = t[y].fa, k = (t[y].ch[1] == x);

  if(n_root(y)) t[z].ch[t[z].ch[1] == y] = x; t[x].fa = z;

  t[y].ch[k] = t[x].ch[k ^ 1]; t[t[x].ch[k ^ 1]].fa = y;

  t[x].ch[k ^ 1] = y; t[y].fa = x;

  pushup(y), pushup(x);

}

int st[maxn], top = 0;

void splay(int x)

{

  int y = x;

  st[top = 1] = y;

  while(n_root(y)) y = t[y].fa, st[++top] = y;

  while(top) pushdown(st[top--]);

  while(n_root(x))

    {

      int y = t[x].fa, z = t[y].fa;

      if(n_root(y))

	{

	  if((t[z].ch[0] == y) ^ (t[y].ch[0] == x)) rotate(x);

	  else rotate(y);

	}

      rotate(x);

    }

}

void access(int x)  //access后,x为splay根节点,且x无右儿子

{

  int y = 0;

  while(x)

    {

      splay(x); t[x].ch[1] = y;

      pushup(x);

      y = x; x = t[x].fa;

    }

}

void make_root(int x)

{

  access(x); splay(x);

  change(x);

}

int find_root(int x)

{

  access(x); splay(x);

  while(t[x].ch[0]) pushdown(x), x = t[x].ch[0];

  return x;

}

void split(int x, int y)  //提取x到y这条链

{

  make_root(x);

  access(y); splay(y); //splay(y):更新链上信息,因为没有记录根节点,所以还得返回y

}

void Link(int x, int y)

{

  make_root(x);

  if(find_root(y) != x) t[x].fa = y;

}

void Cut(int x, int y)

{

  make_root(x);

  if(find_root(y) == x && t[x].fa == y && !t[x].ch[1]) //t[x].ch[1] = 0:x和y之间没有其他点

    {

      t[x].fa = t[y].ch[0] = 0;  //find_root(y)后,y此时是x的父亲

      pushup(y);

    }

}

int main()

{

  n = read(); m = read();

  for(int i = 1; i <= n; ++i) t[i].val = t[i].sum = read();

  for(int i = 1; i <= m; ++i)

    {

      int op = read(), x = read(), y = read();

      if(!op) split(x, y), write(t[y].sum), enter;

      else if(op == 1) Link(x, y);

      else if(op == 2) Cut(x, y);

      else splay(x), t[x].val = y;

    }

  return 0;

}

巴特西

luogu P3690 【模板】Link Cut Tree （动态树）

最新文章

热门文章