Link Cut Tree

Árbol Splay

Recursos
Fuente	Recurso	Notas
MIT	Splay Tree Notes
Stanford	Splay Tree Presentation
CMU	Splay Tree Paper
GH	Splay Tree Implementation

Un árbol splay (splay tree) es un tipo de árbol binario de búsqueda auto-balanceado que soporta implementación eficiente de operaciones como hallar un elemento, borrar un elemento, partir un árbol y unir dos árboles.

Cuando se accede a un nodo en un árbol splay, se realiza una operación splay sobre el nodo que lo mueve a la raíz del árbol a la vez que balancea aproximadamente el árbol.

Link Cut Tree

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	SPOJ	Dynamic Connectivity	Muy fácil	LCT	en el módulo

Recursos
Fuente	Recurso	Notas
MIT	Dynamic Graphs Lecture - Link Cut Trees and HLD
MIT	Dynamic Graphs Scribe Notes
CTSC	Link-Cut Tree Exploration
CF	Link Cut Tree Tutorial
Benq	Link Cut Tree Implementation
CF	Fully Dynamic Trees Supporting Path/Subtree Aggregates

Un Link Cut Tree (LCT) es una estructura de datos que usa árboles splay para representar un bosque de árboles enraizados y puede realizar las siguientes operaciones con una cota superior amortizada de $\mathcal{O}(\log N)$ :

Enlazar un árbol con un nodo haciendo que la raíz del árbol sea hijo de cualquier nodo de otro árbol
Borrar la arista entre un nodo y su padre, desprendiendo el subárbol del nodo para formar un árbol nuevo
Hallar la raíz del árbol al que pertenece un nodo

Estas operaciones usan todas la subrutina $\texttt{access}(v)$ , que crea un camino preferido de la raíz del árbol representado al vértice $v$ , formando un árbol splay auxiliar correspondiente con $v$ como raíz.

Solución

Con Link Cut Tree

Podemos usar un Link Cut Tree para procesar cada tipo de consulta en $\mathcal{O}(\log N)$ . Agregar una arista o quitar una arista entre dos vértices son características estándar del Link Cut Tree.

Comprobar si hay un camino entre dos nodos es lo mismo que comprobar si forman parte del mismo árbol. Para comprobar si dos nodos forman parte del mismo árbol, podemos comprobar si las raíces de los árboles de los dos nodos son las mismas.

Implementación

C++


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Link Cut Tree}
struct Node {
	int x;
	Node *l = 0;
	Node *r = 0;
	Node *p = 0;
	bool rev = false;
 
	Node() = default;
 
	Node(int v) { x = v; }
 
	void push() {
		if (rev) {
			rev = false;
			swap(l, r);
			if (l) l->rev ^= true;
			if (r) r->rev ^= true;
		}
	}
 
	bool is_root() { return p == 0 || (p->l != this && this != p->r); }
};
 
struct LCT {
	vector<Node> a;
 
	LCT(int n) {
		a.resize(n + 1);
		for (int i = 1; i <= n; ++i) a[i].x = i;
	}
 
	void rot(Node *c) {
		auto p = c->p;
		auto g = p->p;
 
		if (!p->is_root()) (g->r == p ? g->r : g->l) = c;
 
		p->push();
		c->push();
 
		if (p->l == c) {  // rtr
			p->l = c->r;
			c->r = p;
			if (p->l) p->l->p = p;
		} else {  // rtl
			p->r = c->l;
			c->l = p;
			if (p->r) p->r->p = p;
		}
 
		p->p = c;
		c->p = g;
	}
 
	void splay(Node *c) {
		while (!c->is_root()) {
			auto p = c->p;
			auto g = p->p;
			if (!p->is_root()) rot((g->r == p) == (p->r == c) ? p : c);
			rot(c);
		}
		c->push();
	}
 
	Node *access(int v) {
		Node *last = 0;
		Node *c = &a[v];
		for (Node *p = c; p; p = p->p) {
			splay(p);
			p->r = last;
			last = p;
		}
		splay(c);
		return last;
	}
 
	void make_root(int v) {
		access(v);
		auto *c = &a[v];
		if (c->l) c->l->rev ^= true, c->l = 0;
	}
 
	void link(int u, int v) {
		make_root(v);
		Node *c = &a[v];
		c->p = &a[u];
	}
 
	void cut(int u, int v) {
		make_root(u);
		access(v);
		if (a[v].l) {
			a[v].l->p = 0;
			a[v].l = 0;
		}
	}
 
	bool connected(int u, int v) {
		access(u);
		access(v);
		return a[u].p;
	}
};
// EndCodeSnip
 
int main() {
	int n;
	int m;
	cin >> n >> m;
	LCT lc(n);
 
	for (int i = 0; i < m; i++) {
		string a;
		cin >> a;
		int b, c;
		cin >> b >> c;
		if (a == "add") { lc.link(b, c); }
		if (a == "rem") { lc.cut(b, c); }
		if (a == "conn") { cout << (lc.connected(b, c) ? "YES" : "NO") << "\n"; }
	}
}

Con Euler Tour Tree

Una solución alternativa es usar la técnica de Euler Tour Tree (ETT), que se construye sobre nuestra técnica de tour de Euler existente guardando el tour de Euler del árbol en un árbol binario de búsqueda balanceado en lugar de un arreglo.

Recursos
Fuente	Recurso	Notas
CF	Euler Tour Tree Introduction
CF	Euler Tour Tree Tutorial

C++


// CodeSnip{Benq Template}
// BeginCodeSnip{Euler Tour Tree}
/**
 * Description: Euler Tour Tree using treap, each edge is
 * represented by two nodes. Supports reroot, insert edge,
 * delete edge, get connected component. Can support
 * aggregate over vertices in connected component by
 * introducing self-loops.
 * Time: O(\log N)
 * Source:
 * https://codeforces.com/blog/entry/53265 (Rerooting dynamic Euler tour trees)
 * https://codeforces.com/blog/entry/18369 (On Euler tour trees)
 * Verification:
 * https://www.spoj.com/problems/DYNACON1/
 */
 
// TREAP OPERATIONS
int cnt, pri[MX], par[MX];  // ETT node for each edge
AR<int, 2> c[MX];
 
int getRoot(int x) {  // get top node in ETT
	while (par[x]) x = par[x];
	return x;
}
void link(int x, int d, int y) {  // set d-th child of x to y
	assert(x);
	assert(d == 0 || d == 1);
	assert(!c[x][d]), c[x][d] = y;
	if (y) assert(!par[y]), par[y] = x;
}
int dis(int x, int d) {  // disconnected d-th child of x
	assert(x);
	assert(d == 0 || d == 1);
	int y = c[x][d];
	c[x][d] = 0;
	if (y) assert(par[y] == x), par[y] = 0;
	return y;
}
pi split(int x) {  // x and everything to right goes in p.s
	// everything else goes in p.f
	pi p = {dis(x, 0), x};
	while (par[x]) {
		int y = par[x];
		if (c[y][0] == x) {
			dis(y, 0), link(y, 0, p.s), p.s = y;
		} else {
			assert(c[y][1] == x);
			dis(y, 1), link(y, 1, p.f);
			p.f = y;
		}
		x = y;
	}
	assert(!par[p.f] && !par[p.s]);
	return p;
}
 
int merge(int x, int y) {
	assert(!par[x] && !par[y]);
	if (!x || !y) return max(x, y);
	if (pri[x] > pri[y]) {
		int X = dis(x, 1);
		link(x, 1, merge(X, y));
		return x;
	} else {
		int Y = dis(y, 0);
		link(y, 0, merge(x, Y));
		return y;
	}
}
 
// int getFirst(int x) {
// 	if (!x) return 0;
// 	while (c[x][0]) x = c[x][0];
// 	return x;
// }
int makeFirst(int x) {  // rotate ETT of x such that x is first
	assert(x);
	pi p = split(x);
	return merge(p.s, p.f);
}
void remFirst(int x) {  // remove first node of ETT rooted at x
	assert(x && !par[x]);
	while (c[x][0]) x = c[x][0];
	int y = dis(x, 1), p = par[x];
	if (p) dis(p, 0), link(p, 0, y);
}
 
// ETT OPERATIONS
map<int, int> adj[MX];
int makeEdge(int a, int b) {
	adj[a][b] = ++cnt;
	pri[cnt] = rng();
	return cnt;
}
int reroot(int x) {  // make edge beginning with x
	if (!sz(adj[x])) return 0;
	return makeFirst(begin(adj[x])->s);
}
bool con(int a, int b) {
	if (!sz(adj[a]) || !sz(adj[b])) return 0;
	a = begin(adj[a])->s, b = begin(adj[b])->s;
	return getRoot(a) == getRoot(b);
}
void add(int a, int b) {  // connect A and B with edge
	int ta = reroot(a), tb = reroot(b);
	if (ta || tb) assert(ta != tb);
	int x = makeEdge(a, b), y = makeEdge(b, a);  // make two nodes for new edge
	merge(merge(ta, x), merge(tb, y));
}
void rem(int a, int b) {
	int x = adj[a][b], y = adj[b][a];
	makeFirst(x);
	pi p = split(y);  // assert(getFirst(p.f) == x && getFirst(p.s) == y);
	remFirst(p.f), remFirst(p.s);
	adj[a].erase(b), adj[b].erase(a);
}
// EndCodeSnip
 
int main() {
	int N, M;
	re(N, M);
	F0R(i, M) {
		str s;
		int A, B;
		re(s, A, B);
		if (s == "add") {
			add(A, B);
		} else if (s == "rem") {
			rem(A, B);
		} else {
			if (con(A, B)) ps("YES");
			else ps("NO");
		}
	}
}

Hallar conectividad

El Link Cut Tree se puede usar para resolver problemas que tratan consultas que actualizan árboles y consultan conectividad.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	SPOJ	Dynamic LCA	Normal	LCT	en el módulo

Explicación

El ancestro común más bajo de dos nodos se halla primero haciendo un camino preferido de la raíz a un nodo y luego al otro. Después de hacer splay del primer nodo, el ancestro común más bajo es simplemente el padre del primer nodo.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
// BeginCodeSnip{Benq Link Cut Tree}
typedef struct snode *sn;
struct snode {         //////// VARIABLES
	sn p, c[2];        // parent, children
	bool flip = 0;     // subtree flipped or not
	int sz;            // # nodes in current splay tree
	ll sub, vsub = 0;  // vsub stores sum of virtual children
	ll val;            // value in node
	snode(int _val) : val(_val) {
		p = c[0] = c[1] = NULL;
		calc();
	}
	friend int getSz(sn x) { return x ? x->sz : 0; }
	friend ll getSub(sn x) { return x ? x->sub : 0; }
	void prop() {  // lazy prop
		if (!flip) return;
		swap(c[0], c[1]);
		flip = 0;
		for (int i = 0; i < 2; i++)
			if (c[i]) c[i]->flip ^= 1;
	}
	void calc() {  // recalc vals
		for (int i = 0; i < 2; i++)
			if (c[i]) c[i]->prop();
		sz = 1 + getSz(c[0]) + getSz(c[1]);
		sub = val + getSub(c[0]) + getSub(c[1]) + vsub;
	}
	//////// SPLAY TREE OPERATIONS
	int dir() {
		if (!p) return -2;
		for (int i = 0; i < 2; i++)
			if (p->c[i] == this) return i;
		return -1;  // p is path-parent pointer
	}  // -> not in current splay tree
	// test if root of current splay tree
	bool isRoot() { return dir() < 0; }
	friend void setLink(sn x, sn y, int d) {
		if (y) y->p = x;
		if (d >= 0) x->c[d] = y;
	}
	void rot() {  // assume p and p->p propagated
		assert(!isRoot());
		int x = dir();
		sn pa = p;
		setLink(pa->p, this, pa->dir());
		setLink(pa, c[x ^ 1], x);
		setLink(this, pa, x ^ 1);
		pa->calc();
	}
	void splay() {
		while (!isRoot() && !p->isRoot()) {
			p->p->prop(), p->prop(), prop();
			dir() == p->dir() ? p->rot() : rot();
			rot();
		}
		if (!isRoot()) p->prop(), prop(), rot();
		prop();
		calc();
	}
	sn fbo(int b) {  // find by order
		prop();
		int z = getSz(c[0]);  // of splay tree
		if (b == z) {
			splay();
			return this;
		}
		return b < z ? c[0]->fbo(b) : c[1]->fbo(b - z - 1);
	}
	//////// BASE OPERATIONS
	void access() {  // bring this to top of tree, propagate
		for (sn v = this, pre = NULL; v; v = v->p) {
			v->splay();  // now switch virtual children
			if (pre) v->vsub -= pre->sub;
			if (v->c[1]) v->vsub += v->c[1]->sub;
			v->c[1] = pre;
			v->calc();
			pre = v;
		}
		splay();
		assert(!c[1]);  // right subtree is empty
	}
	void makeRoot() {
		access();
		flip ^= 1;
		access();
		assert(!c[0] && !c[1]);
	}
	//////// QUERIES
	friend sn lca(sn x, sn y) {
		if (x == y) return x;
		x->access(), y->access();
		if (!x->p) return NULL;
		x->splay();
		return x->p ?: x;  // y was below x in latter case
	}  // access at y did not affect x -> not connected
	friend bool connected(sn x, sn y) { return lca(x, y); }
	// # nodes above
	int distRoot() {
		access();
		return getSz(c[0]);
	}
	sn getRoot() {  // get root of LCT component
		access();
		sn a = this;
		while (a->c[0]) a = a->c[0], a->prop();
		a->access();
		return a;
	}
	sn getPar(int b) {  // get b-th parent on path to root
		access();
		b = getSz(c[0]) - b;
		assert(b >= 0);
		return fbo(b);
	}  // can also get min, max on path to root, etc
	//////// MODIFICATIONS
	void set(int v) {
		access();
		val = v;
		calc();
	}
	friend void link(sn x, sn y, bool force = 0) {
		assert(!connected(x, y));
		if (force) y->makeRoot();  // make x par of y
		else {
			y->access();
			assert(!y->c[0]);
		}
		x->access();
		setLink(y, x, 0);
		y->calc();
	}
	friend void cut(sn y) {  // cut y from its parent
		y->access();
		assert(y->c[0]);
		y->c[0]->p = NULL;
		y->c[0] = NULL;
		y->calc();
	}
	friend void cut(sn x, sn y) {  // if x, y adj in tree
		x->makeRoot();
		y->access();
		assert(y->c[0] == x && !x->c[0] && !x->c[1]);
		cut(y);
	}
};
// EndCodeSnip
 
const int MAX_N = 1e5;
sn LCT[MAX_N];
 
int main() {
	int n;
	int q;
	cin >> n >> q;
	for (int i = 0; i < n; i++) { LCT[i] = new snode(i + 1); }
 
	for (int i = 0; i < q; i++) {
		string t;
		cin >> t;
		if (t == "link") {
			int u, v;
			cin >> u >> v;
			u--, v--;
			link(LCT[v], LCT[u], 1);
		} else if (t == "cut") {
			int u;
			cin >> u;
			u--;
			cut(LCT[u]);
		} else if (t == "lca") {
			int u, v;
			cin >> u >> v;
			u--, v--;
			cout << lca(LCT[u], LCT[v])->val << "\n";
		}
	}
}

Link Cut Tree - Caminos

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Vertex Add Path Sum	Fácil	LCT	en el módulo

Explicación

Un LC Tree también puede calcular el agregado (máximo, mínimo, suma, etc.) de los pesos de las aristas o nodos en un camino.

Para hacer esto, podemos definir una función que devolverá un agregado para el camino de la raíz del árbol al vértice dado. Podemos aumentar los árboles splay auxiliares con el(los) valor(es) que queremos rastrear. El agregado para el camino de la raíz de un árbol a un vértice se puede hallar recuperando el(los) valor(es) del árbol splay creado después de acceder al vértice.

Implementación

Complejidad temporal: $\mathcal{O}(Q\log N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
// BeginCodeSnip{Benq Link Cut Tree}
typedef struct snode *sn;
struct snode {         //////// VARIABLES
	sn p, c[2];        // parent, children
	bool flip = 0;     // subtree flipped or not
	int sz;            // # nodes in current splay tree
	ll sub, vsub = 0;  // vsub stores sum of virtual children
	ll val;            // value in node
	ll sum;
	snode(int _val) : val(_val) {
		p = c[0] = c[1] = NULL;
		calc();
	}
	friend int getSz(sn x) { return x ? x->sz : 0; }
	friend ll getSub(sn x) { return x ? x->sub : 0; }
	friend ll getSum(sn x) { return x ? x->sum : 0; }
	void prop() {  // lazy prop
		if (!flip) return;
		swap(c[0], c[1]);
		flip = 0;
		for (int i = 0; i < 2; i++)
			if (c[i]) c[i]->flip ^= 1;
	}
	void calc() {  // recalc vals
		for (int i = 0; i < 2; i++)
			if (c[i]) c[i]->prop();
		sz = 1 + getSz(c[0]) + getSz(c[1]);
		sub = val + getSub(c[0]) + getSub(c[1]) + vsub;
		sum = val + getSum(c[0]) + getSum(c[1]);
	}
	//////// SPLAY TREE OPERATIONS
	int dir() {
		if (!p) return -2;
		for (int i = 0; i < 2; i++)
			if (p->c[i] == this) return i;
		return -1;  // p is path-parent pointer
	}  // -> not in current splay tree
	// test if root of current splay tree
	bool isRoot() { return dir() < 0; }
	friend void setLink(sn x, sn y, int d) {
		if (y) y->p = x;
		if (d >= 0) x->c[d] = y;
	}
	void rot() {  // assume p and p->p propagated
		assert(!isRoot());
		int x = dir();
		sn pa = p;
		setLink(pa->p, this, pa->dir());
		setLink(pa, c[x ^ 1], x);
		setLink(this, pa, x ^ 1);
		pa->calc();
	}
	void splay() {
		while (!isRoot() && !p->isRoot()) {
			p->p->prop(), p->prop(), prop();
			dir() == p->dir() ? p->rot() : rot();
			rot();
		}
		if (!isRoot()) p->prop(), prop(), rot();
		prop();
		calc();
	}
	sn fbo(int b) {  // find by order
		prop();
		int z = getSz(c[0]);  // of splay tree
		if (b == z) {
			splay();
			return this;
		}
		return b < z ? c[0]->fbo(b) : c[1]->fbo(b - z - 1);
	}
	//////// BASE OPERATIONS
	void access() {  // bring this to top of tree, propagate
		for (sn v = this, pre = NULL; v; v = v->p) {
			v->splay();  // now switch virtual children
			if (pre) v->vsub -= pre->sub;
			if (v->c[1]) v->vsub += v->c[1]->sub;
			v->c[1] = pre;
			v->calc();
			pre = v;
		}
		splay();
		assert(!c[1]);  // right subtree is empty
	}
	void makeRoot() {
		access();
		flip ^= 1;
		access();
		assert(!c[0] && !c[1]);
	}
	//////// QUERIES
	friend sn lca(sn x, sn y) {
		if (x == y) return x;
		x->access(), y->access();
		if (!x->p) return NULL;
		x->splay();
		return x->p ?: x;  // y was below x in latter case
	}  // access at y did not affect x -> not connected
	friend bool connected(sn x, sn y) { return lca(x, y); }
	// # nodes above
	int distRoot() {
		access();
		return getSz(c[0]);
	}
	sn getRoot() {  // get root of LCT component
		access();
		sn a = this;
		while (a->c[0]) a = a->c[0], a->prop();
		a->access();
		return a;
	}
	sn getPar(int b) {  // get b-th parent on path to root
		access();
		b = getSz(c[0]) - b;
		assert(b >= 0);
		return fbo(b);
	}  // can also get min, max on path to root, etc
	//////// MODIFICATIONS
	void set(int v) {
		access();
		val = v;
		calc();
	}
	friend void link(sn x, sn y, bool force = 0) {
		assert(!connected(x, y));
		if (force) y->makeRoot();  // make x par of y
		else {
			y->access();
			assert(!y->c[0]);
		}
		x->access();
		setLink(y, x, 0);
		y->calc();
	}
	friend void cut(sn y) {  // cut y from its parent
		y->access();
		assert(y->c[0]);
		y->c[0]->p = NULL;
		y->c[0] = NULL;
		y->calc();
	}
	friend void cut(sn x, sn y) {  // if x, y adj in tree
		x->makeRoot();
		y->access();
		assert(y->c[0] == x && !x->c[0] && !x->c[1]);
		cut(y);
	}
};
// EndCodeSnip
 
const int MAX_N = 2e5;
sn LCT[MAX_N];
 
int main() {
	int n;
	int q;
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		LCT[i] = new snode(a);
	}
 
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		link(LCT[u], LCT[v], 1);
	}
 
	for (int i = 0; i < q; i++) {
		int t;
		cin >> t;
		if (t == 0) {
			int u, v, w, x;
			cin >> u >> v >> w >> x;
			cut(LCT[u], LCT[v]);
			link(LCT[w], LCT[x], 1);
		} else if (t == 1) {
			int p, x;
			cin >> p >> x;
			LCT[p]->access();
			LCT[p]->val += x;
			LCT[p]->calc();
		} else if (t == 2) {
			int u, v;
			cin >> u >> v;
			LCT[u]->makeRoot();
			LCT[v]->access();
			cout << LCT[v]->sum << "\n";
		}
	}
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
YS	Vertex Add Path Composite	Fácil	LCT	—
Wesley's Anger Contest	Squirrel Cities	Normal	LCT	—
HR	Balanced Tokens	Normal	LCT	—
CEOI	2011 - Treasure Hunt	Normal	LCT	Solución
Baltic OI	2020 - Joker	Difícil	LCT	—
DMOJ	Dynamic Tree Test (Easy)	Difícil	LCT	—
CF	Train Tracking	Difícil	LCT	—
CF	Tree or not Tree	Difícil	LCT	—
CF	CERC 17 D	Difícil	LCT	—
IOI	2011 - Dancing Elephants	Difícil		—

Link Cut Tree - Subárboles

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	YS	Vertex Add Subtree Sum	Normal	LCT	en el módulo

Recursos
Fuente	Recurso	Notas
CF	ouuan - Maintaining Subtree Info

Explicación

También podemos mantener información sobre subárboles rastreando valores para los subárboles virtuales de un nodo. Al consultar información como la suma de subárbol, llamamos access sobre el nodo de modo que todos sus hijos en el árbol representado formen parte de subárboles virtuales y luego recuperamos el valor deseado.

Implementación

Complejidad temporal: $\mathcal{O}(Q\log N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
// BeginCodeSnip{Benq Link Cut Tree}
typedef struct snode *sn;
struct snode {         //////// VARIABLES
	sn p, c[2];        // parent, children
	bool flip = 0;     // subtree flipped or not
	int sz;            // # nodes in current splay tree
	ll sub, vsub = 0;  // vsub stores sum of virtual children
	ll val;            // value in node
	snode(int _val) : val(_val) {
		p = c[0] = c[1] = NULL;
		calc();
	}
	friend int getSz(sn x) { return x ? x->sz : 0; }
	friend ll getSub(sn x) { return x ? x->sub : 0; }
	void prop() {  // lazy prop
		if (!flip) return;
		swap(c[0], c[1]);
		flip = 0;
		for (int i = 0; i < 2; i++)
			if (c[i]) c[i]->flip ^= 1;
	}
	void calc() {  // recalc vals
		for (int i = 0; i < 2; i++)
			if (c[i]) c[i]->prop();
		sz = 1 + getSz(c[0]) + getSz(c[1]);
		sub = val + getSub(c[0]) + getSub(c[1]) + vsub;
	}
	//////// SPLAY TREE OPERATIONS
	int dir() {
		if (!p) return -2;
		for (int i = 0; i < 2; i++)
			if (p->c[i] == this) return i;
		return -1;  // p is path-parent pointer
	}  // -> not in current splay tree
	// test if root of current splay tree
	bool isRoot() { return dir() < 0; }
	friend void setLink(sn x, sn y, int d) {
		if (y) y->p = x;
		if (d >= 0) x->c[d] = y;
	}
	void rot() {  // assume p and p->p propagated
		assert(!isRoot());
		int x = dir();
		sn pa = p;
		setLink(pa->p, this, pa->dir());
		setLink(pa, c[x ^ 1], x);
		setLink(this, pa, x ^ 1);
		pa->calc();
	}
	void splay() {
		while (!isRoot() && !p->isRoot()) {
			p->p->prop(), p->prop(), prop();
			dir() == p->dir() ? p->rot() : rot();
			rot();
		}
		if (!isRoot()) p->prop(), prop(), rot();
		prop();
		calc();
	}
	sn fbo(int b) {  // find by order
		prop();
		int z = getSz(c[0]);  // of splay tree
		if (b == z) {
			splay();
			return this;
		}
		return b < z ? c[0]->fbo(b) : c[1]->fbo(b - z - 1);
	}
	//////// BASE OPERATIONS
	void access() {  // bring this to top of tree, propagate
		for (sn v = this, pre = NULL; v; v = v->p) {
			v->splay();  // now switch virtual children
			if (pre) v->vsub -= pre->sub;
			if (v->c[1]) v->vsub += v->c[1]->sub;
			v->c[1] = pre;
			v->calc();
			pre = v;
		}
		splay();
		assert(!c[1]);  // right subtree is empty
	}
	void makeRoot() {
		access();
		flip ^= 1;
		access();
		assert(!c[0] && !c[1]);
	}
	//////// QUERIES
	friend sn lca(sn x, sn y) {
		if (x == y) return x;
		x->access(), y->access();
		if (!x->p) return NULL;
		x->splay();
		return x->p ?: x;  // y was below x in latter case
	}  // access at y did not affect x -> not connected
	friend bool connected(sn x, sn y) { return lca(x, y); }
	// # nodes above
	int distRoot() {
		access();
		return getSz(c[0]);
	}
	sn getRoot() {  // get root of LCT component
		access();
		sn a = this;
		while (a->c[0]) a = a->c[0], a->prop();
		a->access();
		return a;
	}
	sn getPar(int b) {  // get b-th parent on path to root
		access();
		b = getSz(c[0]) - b;
		assert(b >= 0);
		return fbo(b);
	}  // can also get min, max on path to root, etc
	//////// MODIFICATIONS
	void set(int v) {
		access();
		val = v;
		calc();
	}
	friend void link(sn x, sn y, bool force = 0) {
		assert(!connected(x, y));
		if (force) y->makeRoot();  // make x par of y
		else {
			y->access();
			assert(!y->c[0]);
		}
		x->access();
		setLink(y, x, 0);
		y->calc();
	}
	friend void cut(sn y) {  // cut y from its parent
		y->access();
		assert(y->c[0]);
		y->c[0]->p = NULL;
		y->c[0] = NULL;
		y->calc();
	}
	friend void cut(sn x, sn y) {  // if x, y adj in tree
		x->makeRoot();
		y->access();
		assert(y->c[0] == x && !x->c[0] && !x->c[1]);
		cut(y);
	}
};
// EndCodeSnip
 
const int MAX_N = 2e5;
sn LCT[MAX_N];
 
int main() {
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		LCT[i] = new snode(a);
	}
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		link(LCT[u], LCT[v], 1);
	}
	for (int i = 0; i < q; i++) {
		int t;
		cin >> t;
		if (t == 0) {
			int u, v, w, x;
			cin >> u >> v >> w >> x;
			cut(LCT[u], LCT[v]);
			link(LCT[w], LCT[x], 1);
		} else if (t == 1) {
			int p, x;
			cin >> p >> x;
			LCT[p]->access();
			LCT[p]->val += x;
			LCT[p]->calc();
		} else if (t == 2) {
			int v, p;
			cin >> v >> p;
			LCT[p]->makeRoot();
			LCT[v]->access();
			cout << LCT[v]->vsub + LCT[v]->val << "\n";
		}
	}
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CF	Pastoral Oddities	Normal	LCT	—
YS	Subtree Add Subtree Sum	Difícil	LCT	—
CF	Old Driver Tree	Muy difícil	LCT	—
DMOJ	Dynamic Tree Test	Muy difícil	LCT	—