首页 > 其他分享 >2539. 动态树

2539. 动态树

时间:2022-11-15 17:01:55浏览次数:70  
标签:实边 int tr 原树 splay 2539 动态 节点

题目链接

2539. 动态树

给定 \(n\) 个点,编号从 \(1\) 到 \(n\),其中第 \(i\) 个点的初始权值为 \(a\_i\)。

现在要对这些点进行 \(m\) 次操作,操作共分为以下 \(4\) 种:

  • 0 x y,表示询问点 \(x\) 到点 \(y\) 之间的路径上的所有点(包括两端点)的权值的异或和。保证 \(x\) 和 \(y\) 之间存在连通路径。

  • 1 x y,表示在点 \(x\) 和点 \(y\) 之间增加一条边 \((x,y)\)。注意:如果两点已经处于连通状态,则无视该操作

  • 2 x y,表示删除边 \((x,y)\)。注意:如果该边不存在,则无视该操作

  • 3 x w,表示将点 \(x\) 的权值修改为 \(w\)。

输入格式

第一行包含两个整数 \(n,m\)。

第二行包含 \(n\) 个整数,表示 \(n\) 个点的初始权值。

接下来 \(m\) 行,每行包含一个操作,格式如题目所述。

输出格式

对于每个查询操作 0 x y,输出一个占一行的整数表示答案。

数据范围

\(1 \le n \le 10^5\),
\(1 \le m \le 3 \times 10^5\),
\(1 \le x,y \le n\),
\(x \neq y\),
\(1 \le a_i,w \le 10^9\)

输入样例:

3 6
1 2 3
1 1 2
1 2 3
0 1 3
2 2 3
1 1 3
0 1 3

输出样例:

0
2

解题思路

动态树,LCT

除了删边和加边操作,LCT 的其他操作和树剖一样,可以很灵活地动态定义实边和虚边,在原树中每个节点对于其儿子来说最多只有一条实边,相连的实边极大构成一条实边链,每条实边链用一棵splay来维护,且splay的中序遍历对应原树中实边链从上往下的节点,由于splay的根节点的不存在父亲节点,而除了实边外可能存在一些虚边,splay的根节点的父亲节点正好指向原树中该实边链最上面的节点的父亲节点,进而可以表示虚边。下面是splay的 \(7\) 大函数:

  1. \(isroot(x)\):判断 \(x\) 是所在splay的根节点
    如果 \(x\) 不是splay的根节点,则其一定是其父亲节点的一个儿子

  2. \(access(x)\):建立一条从根到 \(x\) 的实边路径,同时将 \(x\) 变为splay的根节点
    先将 \(x\) 变为所在splay的根节点,则可以找到 \(x\) 所在实边的上面一个节点,即此时 \(x\) 的根节点(此根节点和 \(x\) 是虚边关系),从下往上操作,直接将当前splay接到下一个splay的右子树即可,\(\color{red}{为什么可以这样,不会破坏不相关的其他边的关系吗?}\)由于建立的是一条从根到 \(x\) 的实边路径,由于一个节点与其儿子节点之间最多只能有一条实边,故其他原来是实边的关系都要转换为虚边的关系,假设 \(x\) 所在原树的实边链的最上面一个点和下一条实边链的最下面的一个点 \(y\) 相连,由于splay中的中序遍历的顺序对应原树中从上往下的节点的顺序,从某个点直接断开其和右子树之间的关系,即断开原树中的实边关系,而此时 \(y\) 已经变为所在splay的根节点,其与右子树的关系在原树中应该为虚边关系,此时右子树的根节点在原树中正好对应与 \(y\) 连接的节点,该节点认识 \(y\) 但 \(y\) 此时不认识该节点了,即认父不认子的虚边关系

  3. \(makeroot(x)\):将 \(x\) 变为原树的根节点
    先建立一条从根节点到 \(x\) 的实边路径,然后翻转整条路经,\(\color{red}{翻转是否其他不在该条路径上的节点的信息?}\)其他节点和该条实边路径上的任意一个节点的关系都没有发生改变,所以不会产生影响

  4. \(findroot(x)\):找到 \(x\) 所在原树的根节点,将根节点变为splay的根节点
    先建立一条从根节点到 \(x\) 的实边路径 \(access(x)\),然后一直往左即可

  5. \(split(x,y)\):建立一条从 \(x\) 到 \(y\) 的实边路径,同时将 \(y\) 作为splay的根节点
    先将 \(x\) 变为原树中的根节点 \(makeroot(x)\),再建立一条从根节点到 \(y\) 的实边路径 \(access(y)\)

  6. \(link(x,y)\):\(x\) 和 \(y\) 连边
    先将 \(x\) 变为原树中的根节点 \(makeroot(x)\),如果 \(y\) 所在原树中的根节点 \(findroot(y)\) 不为 \(x\) 的话(即 \(x\) 和 \(y\) 不在同一棵树中且之间没有边)将 \(x\) 的父亲节点指向 \(y\)

  7. \(cut(x,y)\):\(x\) 和 \(y\) 删边
    先将 \(x\) 变为原树中的根节点 \(makeroot(x)\),如果 \(y\) 所在原树中的根节点 \(findroot(y)\) (此时 \(x\) 作为splay的根节点)为 \(x\) 的话,由于此时 \(x\) 即作为原树的根节点,又作为splay的根节点,即 \(x\) 在splay中只有后继,如果 \(x\) 和 \(y\) 之间有边的话,只可能 \(y\) 是 \(x\) 的右子树且 \(y\) 没有左子树

在splay中维护需要维护的信息即可

  • 时间复杂度:\(O(mlogn)\)

代码

// Problem: 动态树
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2541/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
int n,m,stk[N];
struct Node
{
	int s[2],p,v;
	int sum,rev;	
}tr[N];
void pushup(int x)
{
	tr[x].sum=tr[tr[x].s[0]].sum^tr[x].v^tr[tr[x].s[1]].sum;
}
void pushrev(int x)
{
	swap(tr[x].s[0],tr[x].s[1]);
	tr[x].rev^=1;
}
void pushdown(int x)
{
	if(tr[x].rev)
	{
		pushrev(tr[x].s[0]),pushrev(tr[x].s[1]);
		tr[x].rev=0;
	}
}
bool isroot(int x)
{
	return tr[tr[x].p].s[0]!=x&&tr[tr[x].p].s[1]!=x;
}
void rotate(int x)
{
	int y=tr[x].p,z=tr[y].p;
	int k=tr[y].s[1]==x;
	if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
	tr[x].p=z;
	tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
	tr[x].s[k^1]=y,tr[y].p=x;
	pushup(y),pushup(x);
}
void splay(int x)
{
	int top=0,r=x;
	stk[++top]=r;
	while(!isroot(r))stk[++top]=r=tr[r].p;
	while(top)pushdown(stk[top--]);
	while(!isroot(x))
	{
		int y=tr[x].p,z=tr[y].p;
		if(!isroot(y))
			if((tr[y].s[1]==x)^(tr[z].s[1]==y))rotate(x);
			else
				rotate(y);
		rotate(x);
	}
}
void access(int x)//建立一条从根到x的实边路径,同时将x变为splay的根节点
{
	int z=x;
	for(int y=0;x;y=x,x=tr[x].p)
	{
		splay(x);
		tr[x].s[1]=y,pushup(x);
	}
	splay(z);
}
void makeroot(int x)//将x变为原树的根节点
{
	access(x);
	pushrev(x);
}
int findroot(int x)//找到x所在原树的根节点,并将根节点变为splay的根节点
{
	access(x);
	while(tr[x].s[0])x=tr[x].s[0];
	splay(x);
	return x;
}
void split(int x,int y)//建立一条从x到y的实边路径,同时将y作为splay的根节点
{
	makeroot(x);
	access(y);
}
void link(int x,int y)
{
	makeroot(x);
	if(findroot(y)!=x)tr[x].p=y;
}
void cut(int x,int y)
{
	makeroot(x);
	if(findroot(y)==x&&tr[y].p==x&&!tr[y].s[0])
	{
		tr[x].s[1]=tr[y].p=0;
		pushup(x);
	}
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&tr[i].v);
    while(m--)
    {
    	int op,x,y;
    	scanf("%d%d%d",&op,&x,&y);
    	if(op==0)
    	{
    		split(x,y);
    		printf("%d\n",tr[y].sum);
    	}
    	else if(op==1)
    		link(x,y);
    	else if(op==2)
    		cut(x,y);
    	else
    	{
    		splay(x);
    		tr[x].v=y;
    		pushup(x);
    	}
    }
    return 0;
}

标签:实边,int,tr,原树,splay,2539,动态,节点
From: https://www.cnblogs.com/zyyun/p/16892997.html

相关文章

  • 报告分享|2022年直播行业研究最新动态
    报告全文链接:http://tecdat.cn/?p=30326中国直播电商起源于2016年,之后大致经历2017-2018年的快速拓展期、2019-2020年的百花齐放期以及2021至今的全民直播三大阶段。中国......
  • mysql动态新增字段
    使用PREPARE预处理语句动态新增字段,先判断表的字段是否存在,如果存在不新增,反之新增。--1.动态新增字段(储存过程);--结束符号DROPprocedureifEXISTSsp_add_col......
  • unity 通过场景名称实现动态加载背景BGM音乐
    在场景中创建一个空物体对象,然后将代码挂载到空物体需要注意的是,场景中需要有以下组件一般在主摄像头里 添加到代码挂载的空物体上将场景中类的公开变量s......
  • 动态语言和静态语言
    概念:动态语言:是运行时才确定数据类型的语言,变量在使用之前无需申明类型,通常变量的值是被赋值的那个值的类型。比如Php、Asp、JavaScript、Python、Perl等等。vars="h......
  • 70. 爬楼梯 ----- 动态规划、滚动数组(技巧动态规划)、数学方法:特征方程、矩阵快速幂
    假设你正在爬楼梯。需要n 阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢? 示例1:输入:n=2输出:2解释:有两种方法可以爬到楼顶......
  • JDK 动态代理
    Factoryclass文件publicclassProxyFactory{ privateObjecttarget; publicProxyFactory(Objecttarget){ super(); this.target=target; } /**......
  • cglib 动态代理
    Factoryclass文件publicclassProxyFactory{ privateObjecttarget; publicProxyFactory(Objecttarget){ super(); this.target=target; } /*......
  • 阿里云微服务引擎 MSE 9 月份产品动态
    ......
  • vue+iviews 动态表格(table组件)
      iviews官网上关于table的使用方法是固定表头的使用方法,如何生成动态的table网上找了好多也没有特别合适的,综合几位博主的文章经过尝试终于实现了,分享出来供大家参考......
  • 动态代理简单代码
     /***业务接口*/publicinterfaceSubject{voidcall();} /***业务接口的实现(被代理的类)*/publicclassRealSubjcetimplementsSubject{......