C++(g++ 7.5.0) 解法, 执行用时: 2551ms, 内存消耗: 181040K, 提交时间: 2022-09-24 11:52:59

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 200005;

struct lct_node {
	lct_node *ch[2], *p;
	int self_size, tree_size;

	lct_node() : self_size(1), tree_size(1) {}

	void update() {
		tree_size = self_size + ch[0] -> tree_size + ch[1] -> tree_size;
	}
} lct_null[maxn];

void lct_init(lct_node *x) {
	*x = lct_node();
	x -> ch[0] = x -> ch[1] = x -> p = lct_null;
}

inline bool isroot(lct_node *x) {
	return x != x -> p -> ch[0] && x != x -> p -> ch[1];
}

inline int dir(lct_node *x) {
	return x == x -> p -> ch[1];
}

void lct_rotate(lct_node *x, int d) {
	lct_node *y = x -> ch[d ^ 1];

	y -> p = x -> p;
	if (!isroot(x))
		x -> p -> ch[dir(x)] = y;
	
	if ((x -> ch[d ^ 1] = y -> ch[d]) != lct_null)
		y -> ch[d] -> p = x;
	(y -> ch[d] = x) -> p = y;

	x -> update();
	y -> update();
}

void lct_splay(lct_node *x) {
	while (!isroot(x)) {
		if (isroot(x -> p)) {
			lct_rotate(x -> p, dir(x) ^ 1);
			break;
		}

		if (dir(x) == dir(x -> p))
			lct_rotate(x -> p -> p, dir(x -> p) ^ 1);
		else
			lct_rotate(x -> p, dir(x) ^ 1);
		lct_rotate(x -> p, dir(x) ^ 1);
	}
}

lct_node *lct_access(lct_node *x) {
	lct_node *y = lct_null;

	while (x != lct_null) {
		lct_splay(x);

		x -> self_size += x -> ch[1] -> tree_size;
		x -> self_size -= y -> tree_size;
		x -> ch[1] = y;
		(y = x) -> update();

		x = x -> p;
	}

	return y;
}

void lct_link(lct_node *x, lct_node *y) {
	lct_access(y);
	lct_splay(y);
	x -> p = y;
	y -> self_size += x -> tree_size;
	y -> tree_size += x -> tree_size;
}

int lct_query(lct_node *x) {
	lct_access(x);
	return x -> self_size;
}

pair<long long, long long> operator + (const pair<long long, long long> &a, const pair<long long, long long> &b) {
	return {a.first + b.first, a.second + b.second};
}

pair<long long, long long> &operator += (pair<long long, long long> &a, const pair<long long, long long> &b) {
	a.first += b.first;
	a.second += b.second;
	return a;
}

mt19937 rng(233);

struct sbt_node {
	int key, size;
	pair<long long, long long> val, sum;
	sbt_node *ch[2];

	sbt_node(int key, const pair<long long, long long> &val) : key(key), size(1),
		val(val), sum(val) {}

	void update() {
		size = 1 + ch[0] -> size + ch[1] -> size;
		sum = val + ch[0] -> sum + ch[1] -> sum;
	}
} *sbt_null = new sbt_node(0, {0, 0});

sbt_node *new_sbt_node(int key, const pair<long long, long long> &val) {
	sbt_node *x = new sbt_node(key, val);
	x -> ch[0] = x -> ch[1] = sbt_null;
	return x;
}

void sbt_rotate(sbt_node *&x, int d) {
	sbt_node *y = x -> ch[d ^ 1];
	x -> ch[d ^ 1] = y -> ch[d];
	y -> ch[d] = x;
	x -> update();
	(x = y) -> update();
}

void sbt_maintain(sbt_node *&x, int d) {
	if (x -> ch[d] -> ch[d] -> size > x -> ch[d ^ 1] -> size)
		sbt_rotate(x, d ^ 1);
	else if (x -> ch[d] -> ch[d ^ 1] -> size > x -> ch[d ^ 1] -> size) {
		sbt_rotate(x -> ch[d], d);
		sbt_rotate(x, d ^ 1);
	}
	else
		return;
	
	sbt_maintain(x -> ch[0], 0);
	sbt_maintain(x -> ch[1], 1);
	sbt_maintain(x, 0);
	sbt_maintain(x, 1);
}

void sbt_insert(sbt_node *&x, int k, const pair<long long, long long> &v) {
	if (x == sbt_null) {
		x = new_sbt_node(k, v);
		return;
	}
	
	if (k == x -> key) {
		x -> val += v;
		x -> sum += v;
		return;
	}

	int d = (k > x -> key);
	sbt_insert(x -> ch[d], k, v);
	x -> update();
	sbt_maintain(x, d);
}

void sbt_travel(sbt_node *x, vector<pair<int, pair<long long, long long> > > &vec) {
	if (x == sbt_null)
		return;

	sbt_travel(x -> ch[0], vec);
	vec.emplace_back(x -> key, x -> val);
	sbt_travel(x -> ch[1], vec);
}

void sbt_destroy(sbt_node *&x) {
	if (x == sbt_null)
		return;
	
	sbt_destroy(x -> ch[0]);
	sbt_destroy(x -> ch[1]);
	delete x;
	x = sbt_null;
}

void sbt_build(sbt_node *&x, int l, int r, const vector<pair<int, pair<long long, long long> > > &vec) {
	if (l > r) {
		x = sbt_null;
		return;
	}

	int mid = (l + r) / 2;

	x = new_sbt_node(vec[mid].first, vec[mid].second);

	sbt_build(x -> ch[0], l, mid - 1, vec);
	sbt_build(x -> ch[1], mid + 1, r, vec);

	x -> update();
}

pair<long long, long long> sbt_query(const sbt_node *x, int k) {
	if (x == sbt_null)
		return {0, 0ll};
	
	if (k <= x -> key) {
		auto ans = sbt_query(x -> ch[0], k);
		if (k == x -> key)
			ans += x -> val;
		
		return ans;
	}
	else
		return x -> val + x -> ch[0] -> sum + sbt_query(x -> ch[1], k);
}

struct treap_node {
	int size, weight;
	sbt_node *self_root, *tree_root;

	treap_node *ch[2], *p;

	treap_node() : size(1), weight(0), self_root(sbt_null), tree_root(sbt_null) {}

	void update() {
		size = 1 + ch[0] -> size + ch[1] -> size;
		weight = self_root -> size + ch[0] -> weight + ch[1] -> weight;
	}
} *treap_null = new treap_node(), *treap_root = treap_null;

treap_node *new_treap_node() {
	treap_node *x = new treap_node();
	x -> ch[0] = x -> ch[1] = x -> p = treap_null;
	return x;
}

void treap_travel(treap_node *x, vector<treap_node*> &vec) {
	if (x == treap_null)
		return;

	// cerr << "x = " << x << ", size = " << x -> size << endl;
	
	treap_travel(x -> ch[0], vec);

	vec.push_back(x);
	sbt_destroy(x -> tree_root);

	treap_travel(x -> ch[1], vec);
}

vector<pair<int, pair<long long, long long> > > vector_merge(const vector<pair<int, pair<long long, long long> > > &a, const vector<pair<int, pair<long long, long long> > > &b) {
	vector<pair<int, pair<long long, long long> > > c;
	c.reserve(a.size() + b.size());

	auto i = a.begin(), j = b.begin();
	while (i != a.end() && j != b.end()) {
		if (i -> first < j -> first)
			c.push_back(*i++);
		else if (i -> first > j -> first)
			c.push_back(*j++);
		else {
			c.push_back(make_pair(i -> first, i -> second + j -> second));
			i++;
			j++;
		}
	}

	while (i != a.end())
		c.push_back(*i++);
	while (j != b.end())
		c.push_back(*j++);

	return c;
}

vector<pair<int, pair<long long, long long> > > treap_rebuild(treap_node *&x, int l, int r, vector<treap_node*> &vec) {
	if (l > r) {
		x = treap_null;
		return {};
	}
	
	int mid = (l + r) / 2;
	x = vec[mid];

	auto u = move(treap_rebuild(x -> ch[0], l, mid - 1, vec));
	if (x -> ch[0] != treap_null)
		x -> ch[0] -> p = x;
	
	auto v = move(treap_rebuild(x -> ch[1], mid + 1, r, vec));
	if (x -> ch[1] != treap_null)
		x -> ch[1] -> p = x;
	
	vector<pair<int, pair<long long, long long> > > vt;
	sbt_travel(x -> self_root, vt);
	
	auto res = vector_merge(vector_merge(u, v), vt);
	sbt_build(x -> tree_root, 0, (int)res.size() - 1, res);
	
	x -> update();
	// cerr << "now x(" << x << ") -> size = " << x -> size << endl;

	return res;
}

int treap_rank(treap_node *x) { // 1-based
	if (x == treap_null)
		return 0;

	int ans = x -> ch[0] -> size + 1;

	while (x -> p != treap_null) {
		if (x == x -> p -> ch[1])
			ans += x -> p -> ch[0] -> size + 1;
		
		x = x -> p;
	}

	return ans;
}

treap_node *treap_find(int k, treap_node *x = treap_root) {
	while (x != treap_null) {
		if (k == x -> ch[0] -> size + 1)
			return x;
		
		int d = (k > x -> ch[0] -> size + 1);
		if (d)
			k -= x -> ch[0] -> size + 1;
		
		x = x -> ch[d];
	}
	
	assert(false);
	return nullptr;
}

void treap_insert(treap_node *x, treap_node *o) { // after o
	if (o -> ch[1] == treap_null) {
		o -> ch[1] = x;
		x -> p = o;
	}
	else {
		o = o -> ch[1];
		while (o -> ch[0] != treap_null)
			o = o -> ch[0];

		o -> ch[0] = x;
		x -> p = o;
	}

	treap_node *goat = treap_null;
	while (o != treap_null) {
		o -> update();

		if ((int)(rng() % (o -> size + o -> weight)) < (x -> size + x -> weight))
			goat = o;
		o = o -> p;
	}
	
	if (goat == treap_null)
		return;

	// cerr << "goat = " << goat << endl;
	
	vector<treap_node*> vec;
	treap_travel(goat, vec);
	// cerr << "vec.size() = " << vec.size() << endl;

	// cerr << "root = " << treap_root << endl;
	if (goat == treap_root) {
		treap_rebuild(treap_root, 0, (int)vec.size() - 1, vec);
		treap_root -> p = treap_null;
		// cerr << "root = " << treap_root << endl;
	}
	else {
		// assert(goat -> p != treap_null);
		treap_node *p = goat -> p;
		int d = (goat == p -> ch[1]);
		treap_rebuild(p -> ch[d], 0, (int)vec.size() - 1, vec);
		p -> ch[d] -> p = p;
	}
}

void treap_modify(treap_node *x, int key, const pair<long long, long long> &val) {
	sbt_insert(x -> self_root, key, val);

	while (x != treap_null) {
		sbt_insert(x -> tree_root, key, val);
		x = x -> p;
	}
}

pair<long long, long long> treap_query(treap_node *x, int l, int r, int key) { // 1-based
	if (x == treap_null)
		return {0, 0ll};
	
	if (l == 1 && r == x -> size)
		return sbt_query(x -> tree_root, key);
	
	int mid = x -> ch[0] -> size + 1;
	
	// cerr << "x = " << x << ", l = " << l << ", r = " << r << ", mid = " << mid << endl;
	
	pair<long long, long long> ans(0, 0ll);
	if (l <= mid && r >= mid)
		ans = sbt_query(x -> self_root, key);
	
	if (l < mid)
		ans += treap_query(x -> ch[0], l, min(mid - 1, r), key);
	if (r > mid)
		ans += treap_query(x -> ch[1], max(1, l - mid), r - mid, key);
	
	return ans;
}

vector<int> G[maxn];
int pr[maxn], d[maxn], f[19][maxn];
int dfn[maxn], tim, id[maxn];
treap_node *treap_id[maxn];

void treap_build(treap_node *&o, int l, int r) {
	if (l > r) {
		o = treap_null;
		return;
	}
	
	int mid = rng() % (r - l + 1) + l;
	treap_id[id[mid]] = o = new treap_node();

	treap_build(o -> ch[0], l, mid - 1);
	if (o -> ch[0] != treap_null)
		o -> ch[0] -> p = o;
	
	treap_build(o -> ch[1], mid + 1, r);
	if (o -> ch[1] != treap_null)
		o -> ch[1] -> p = o;
	
	o -> update();
	// cerr << "o = " << o << "  size = " << o -> size << endl;
}

void dfs(int x) {
	dfn[x] = ++tim;
	id[tim] = x;
	d[x] = d[pr[x]] + 1;

	for (int y : G[x])
		if (y != pr[x]) {
			pr[y] = x;

			dfs(y);

			lct_null[y].p = lct_null + x;
			lct_null[x].self_size += lct_null[y].tree_size;
		}
	
	lct_null[x].tree_size = lct_null[x].self_size;
}

int lca(int x, int y) {
	if (d[x] != d[y]) {
		if (d[x] < d[y])
			swap(x, y);
		
		int t = d[x] - d[y];
		for (int i = 0; i < 19; i++)
			if (t >> i & 1)
				x = f[i][x];
	}
	if (x == y)
		return x;
	
	for (int i = 18; ~i; i--)
		if (f[i][x] != f[i][y]) {
			x = f[i][x];
			y = f[i][y];
		}
	
	return f[0][x];
}

int main() {

	lct_null -> ch[0] = lct_null -> ch[1] = lct_null -> p = lct_null;
	lct_null -> self_size = lct_null -> tree_size = 0;
	treap_null -> ch[0] = treap_null -> ch[1] = treap_null -> p = treap_null;
	treap_null -> size = 0;
	sbt_null -> ch[0] = sbt_null -> ch[1] = sbt_null;
	sbt_null -> size = 0;

	int n, m;
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++)
		lct_init(lct_null + i);

	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);

		G[x].push_back(y);
		G[y].push_back(x);
	}

	dfs(1);

	for (int i = 1; i <= n; i++)
		f[0][i] = pr[i];
	
	for (int j = 1; j < 19; j++)
		for (int i = 1; i <= n; i++)
			f[j][i] = f[j - 1][f[j - 1][i]];
	
	treap_build(treap_root, 1, n);
	treap_root -> p = treap_null;

	int last = 0;

	while (m--) {
		int op;
		scanf("%d", &op);

		if (op == 1) {
			scanf("%d", &pr[++n]);
			pr[n] ^= last;

			d[n] = d[pr[n]] + 1;
			f[0][n] = pr[n];
			for (int j = 1; j < 19; j++)
				f[j][n] = f[j - 1][f[j - 1][n]];
			
			treap_id[n] = new treap_node();
			treap_id[n] -> ch[0] = treap_id[n] -> ch[1] = treap_id[n] -> p = treap_null;
			treap_node *last = treap_find(treap_rank(treap_id[pr[n]]) + lct_query(lct_null + pr[n]) - 1);
			treap_insert(treap_id[n], last);

			lct_init(lct_null + n);
			lct_link(lct_null + n, lct_null + pr[n]);

			// cerr << "--- now ---" << endl;
			// for (int i = 1; i <= n; i++)
			// 	cerr << "i = " << i << "  rank = " << treap_rank(treap_id[i]) << endl;
		}
		else if (op == 2) {
			int x, y, c, k;
			scanf("%d%d%d%d", &x, &y, &c, &k);
			x ^= last;
			y ^= last;
			c ^= last;
			k ^= last;

			int z = lca(x, y);
			// cerr << "x = " << x << "  y = " << y << "  z = " << z << endl;
			treap_modify(treap_id[x], c, {-k, (long long)k * (d[x] + 1)});
			treap_modify(treap_id[y], c, {-k, (long long)k * (d[y] + 1)});
			treap_modify(treap_id[z], c, {2 * k, -k * (long long)(d[x] + d[y] + 2) + (long long)k * (d[x] + d[y] - 2 * d[z] + 1)});
		}
		else {
			int x, c;
			scanf("%d%d", &x, &c);
			x ^= last;
			c ^= last;

			int l = treap_rank(treap_id[x]), r = l + lct_query(lct_null + x) - 1;
			// cerr << "l = " << l << "  r = " << r << endl;
			auto [a, b] = treap_query(treap_root, l, r, c);
			long long ans = a * d[x] + b;
			// cerr << "a = " << a << "  b = " << b << endl;

			printf("%lld\n", ans);

			last = ans & 2147483647;
		}
	}

	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1908ms, 内存消耗: 120180K, 提交时间: 2022-09-23 22:33:33

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 200005;
constexpr double alpha = 0.75;

struct lct_node {
	lct_node *ch[2], *p;
	int self_size, tree_size;

	lct_node() : self_size(1), tree_size(1) {}

	void update() {
		tree_size = self_size + ch[0] -> tree_size + ch[1] -> tree_size;
	}
} lct_null[maxn];

void lct_init(lct_node *x) {
	*x = lct_node();
	x -> ch[0] = x -> ch[1] = x -> p = lct_null;
}

inline bool isroot(lct_node *x) {
	return x != x -> p -> ch[0] && x != x -> p -> ch[1];
}

inline int dir(lct_node *x) {
	return x == x -> p -> ch[1];
}

void lct_rotate(lct_node *x, int d) {
	lct_node *y = x -> ch[d ^ 1];

	y -> p = x -> p;
	if (!isroot(x))
		x -> p -> ch[dir(x)] = y;
	
	if ((x -> ch[d ^ 1] = y -> ch[d]) != lct_null)
		y -> ch[d] -> p = x;
	(y -> ch[d] = x) -> p = y;

	x -> update();
	y -> update();
}

void lct_splay(lct_node *x) {
	while (!isroot(x)) {
		if (isroot(x -> p)) {
			lct_rotate(x -> p, dir(x) ^ 1);
			break;
		}

		if (dir(x) == dir(x -> p))
			lct_rotate(x -> p -> p, dir(x -> p) ^ 1);
		else
			lct_rotate(x -> p, dir(x) ^ 1);
		lct_rotate(x -> p, dir(x) ^ 1);
	}
}

lct_node *lct_access(lct_node *x) {
	lct_node *y = lct_null;

	while (x != lct_null) {
		lct_splay(x);

		x -> self_size += x -> ch[1] -> tree_size;
		x -> self_size -= y -> tree_size;
		x -> ch[1] = y;
		(y = x) -> update();

		x = x -> p;
	}

	return y;
}

void lct_link(lct_node *x, lct_node *y) {
	lct_access(y);
	lct_splay(y);
	x -> p = y;
	y -> self_size += x -> tree_size;
	y -> tree_size += x -> tree_size;
}

int lct_query(lct_node *x) {
	lct_access(x);
	return x -> self_size;
}

pair<long long, long long> operator + (const pair<long long, long long> &a, const pair<long long, long long> &b) {
	return {a.first + b.first, a.second + b.second};
}

pair<long long, long long> &operator += (pair<long long, long long> &a, const pair<long long, long long> &b) {
	a.first += b.first;
	a.second += b.second;
	return a;
}

struct sbt_node {
	int key, size;
	pair<long long, long long> val, sum;
	sbt_node *ch[2];

	sbt_node(int key, const pair<long long, long long> &val) : key(key), size(1),
		val(val), sum(val) {}

	void update() {
		size = 1 + ch[0] -> size + ch[1] -> size;
		sum = val + ch[0] -> sum + ch[1] -> sum;
	}
} *sbt_null = new sbt_node(0, {0, 0});

sbt_node *new_sbt_node(int key, const pair<long long, long long> &val) {
	sbt_node *x = new sbt_node(key, val);
	x -> ch[0] = x -> ch[1] = sbt_null;
	return x;
}

void sbt_rotate(sbt_node *&x, int d) {
	sbt_node *y = x -> ch[d ^ 1];
	x -> ch[d ^ 1] = y -> ch[d];
	y -> ch[d] = x;
	x -> update();
	(x = y) -> update();
}

void sbt_maintain(sbt_node *&x, int d) {
	if (x -> ch[d] -> ch[d] -> size > x -> ch[d ^ 1] -> size)
		sbt_rotate(x, d ^ 1);
	else if (x -> ch[d] -> ch[d ^ 1] -> size > x -> ch[d ^ 1] -> size) {
		sbt_rotate(x -> ch[d], d);
		sbt_rotate(x, d ^ 1);
	}
	else
		return;
	
	sbt_maintain(x -> ch[0], 0);
	sbt_maintain(x -> ch[1], 1);
	sbt_maintain(x, 0);
	sbt_maintain(x, 1);
}

void sbt_insert(sbt_node *&x, int k, const pair<long long, long long> &v) {
	if (x == sbt_null) {
		x = new_sbt_node(k, v);
		return;
	}
	
	if (k == x -> key) {
		x -> val += v;
		x -> sum += v;
		return;
	}

	int d = (k > x -> key);
	sbt_insert(x -> ch[d], k, v);
	x -> update();
	sbt_maintain(x, d);
}

void sbt_travel(sbt_node *x, vector<pair<int, pair<long long, long long> > > &vec) {
	if (x == sbt_null)
		return;

	sbt_travel(x -> ch[0], vec);
	vec.emplace_back(x -> key, x -> val);
	sbt_travel(x -> ch[1], vec);
}

void sbt_destroy(sbt_node *&x) {
	if (x == sbt_null)
		return;
	
	sbt_destroy(x -> ch[0]);
	sbt_destroy(x -> ch[1]);
	delete x;
	x = sbt_null;
}

void sbt_build(sbt_node *&x, int l, int r, const vector<pair<int, pair<long long, long long> > > &vec) {
	if (l > r) {
		x = sbt_null;
		return;
	}

	int mid = (l + r) / 2;

	x = new_sbt_node(vec[mid].first, vec[mid].second);

	sbt_build(x -> ch[0], l, mid - 1, vec);
	sbt_build(x -> ch[1], mid + 1, r, vec);

	x -> update();
}

pair<long long, long long> sbt_query(const sbt_node *x, int k) {
	if (x == sbt_null)
		return {0, 0ll};
	
	if (k <= x -> key) {
		auto ans = sbt_query(x -> ch[0], k);
		if (k == x -> key)
			ans += x -> val;
		
		return ans;
	}
	else
		return x -> val + x -> ch[0] -> sum + sbt_query(x -> ch[1], k);
}

struct treap_node {
	int size, weight;
	sbt_node *self_root, *tree_root;

	treap_node *ch[2], *p;

	treap_node() : size(1), weight(0), self_root(sbt_null), tree_root(sbt_null) {}

	void update() {
		size = 1 + ch[0] -> size + ch[1] -> size;
		weight = self_root -> size + ch[0] -> weight + ch[1] -> weight;
	}
} *treap_null = new treap_node(), *treap_root = treap_null;

treap_node *new_treap_node() {
	treap_node *x = new treap_node();
	x -> ch[0] = x -> ch[1] = x -> p = treap_null;
	return x;
}

void treap_travel(treap_node *x, vector<treap_node*> &vec) {
	if (x == treap_null)
		return;
	
	treap_travel(x -> ch[0], vec);

	vec.push_back(x);
	sbt_destroy(x -> tree_root);

	treap_travel(x -> ch[1], vec);
}

vector<pair<int, pair<long long, long long> > > vector_merge(const vector<pair<int, pair<long long, long long> > > &a, const vector<pair<int, pair<long long, long long> > > &b) {
	vector<pair<int, pair<long long, long long> > > c;
	c.reserve(a.size() + b.size());

	auto i = a.begin(), j = b.begin();
	while (i != a.end() && j != b.end()) {
		if (i -> first < j -> first)
			c.push_back(*i++);
		else if (i -> first > j -> first)
			c.push_back(*j++);
		else {
			c.push_back(make_pair(i -> first, i -> second + j -> second));
			i++;
			j++;
		}
	}

	while (i != a.end())
		c.push_back(*i++);
	while (j != b.end())
		c.push_back(*j++);

	return c;
}

vector<pair<int, pair<long long, long long> > > treap_rebuild(treap_node *&x, int l, int r, vector<treap_node*> &vec) {
	if (l > r) {
		x = treap_null;
		return {};
	}

	int tmp = 1e9, left = 0, right = 0;
	for (int i = l; i <= r; i++)
		right += vec[i] -> self_root -> size + 1;
	
	int mid = -1;
	for (int i = l; i <= r; i++) {
		right -= vec[i] -> self_root -> size + 1;
		int val = max(left, right);

		if (val < tmp) {
			tmp = val;
			mid = i;
		}

		left += vec[i] -> self_root -> size + 1;
	}
	assert(mid >= 0);

	x = vec[mid];

	auto u = move(treap_rebuild(x -> ch[0], l, mid - 1, vec));
	if (x -> ch[0] != treap_null)
		x -> ch[0] -> p = x;
	
	auto v = move(treap_rebuild(x -> ch[1], mid + 1, r, vec));
	if (x -> ch[1] != treap_null)
		x -> ch[1] -> p = x;
	
	vector<pair<int, pair<long long, long long> > > vt;
	sbt_travel(x -> self_root, vt);
	
	auto res = vector_merge(vector_merge(u, v), vt);
	sbt_build(x -> tree_root, 0, (int)res.size() - 1, res);
	
	x -> update();

	return res;
}

int treap_rank(treap_node *x) { // 1-based
	if (x == treap_null)
		return 0;

	int ans = x -> ch[0] -> size + 1;

	while (x -> p != treap_null) {
		if (x == x -> p -> ch[1])
			ans += x -> p -> ch[0] -> size + 1;
		
		x = x -> p;
	}

	return ans;
}

treap_node *treap_find(int k, treap_node *x = treap_root) {
	while (x != treap_null) {
		if (k == x -> ch[0] -> size + 1)
			return x;
		
		int d = (k > x -> ch[0] -> size + 1);
		if (d)
			k -= x -> ch[0] -> size + 1;
		
		x = x -> ch[d];
	}
	
	assert(false);
	return nullptr;
}

void treap_insert(treap_node *x, treap_node *o) { // after o
	if (o -> ch[1] == treap_null) {
		o -> ch[1] = x;
		x -> p = o;
	}
	else {
		o = o -> ch[1];
		while (o -> ch[0] != treap_null)
			o = o -> ch[0];

		o -> ch[0] = x;
		x -> p = o;
	}

	treap_node *goat = treap_null;
	while (o != treap_null) {
		o -> update();

		if (max(o -> ch[0] -> weight + o -> ch[0] -> size, o -> ch[1] -> weight + o -> ch[1] -> size) > (o -> weight + o -> size) * alpha + 5)
			goat = o;

		o = o -> p;
	}
	
	if (goat == treap_null)
		return;
	
	vector<treap_node*> vec;
	treap_travel(goat, vec);

	if (goat == treap_root) {
		treap_rebuild(treap_root, 0, (int)vec.size() - 1, vec);
		treap_root -> p = treap_null;
	}
	else {
		treap_node *p = goat -> p;
		int d = (goat == p -> ch[1]);
		treap_rebuild(p -> ch[d], 0, (int)vec.size() - 1, vec);
		p -> ch[d] -> p = p;
	}
}

void treap_modify(treap_node *x, int key, const pair<long long, long long> &val) {
	sbt_insert(x -> self_root, key, val);

	while (x != treap_null) {
		sbt_insert(x -> tree_root, key, val);
		x = x -> p;
	}
}

pair<long long, long long> treap_query(treap_node *x, int l, int r, int key) { // 1-based
	if (x == treap_null)
		return {0, 0ll};
	
	if (l == 1 && r == x -> size)
		return sbt_query(x -> tree_root, key);
	
	int mid = x -> ch[0] -> size + 1;
	
	pair<long long, long long> ans(0, 0ll);
	if (l <= mid && r >= mid)
		ans = sbt_query(x -> self_root, key);
	
	if (l < mid)
		ans += treap_query(x -> ch[0], l, min(mid - 1, r), key);
	if (r > mid)
		ans += treap_query(x -> ch[1], max(1, l - mid), r - mid, key);
	
	return ans;
}

vector<int> G[maxn];
int pr[maxn], d[maxn], f[19][maxn];
int dfn[maxn], tim, id[maxn];
treap_node *treap_id[maxn];

void treap_build(treap_node *&o, int l, int r) {
	if (l > r) {
		o = treap_null;
		return;
	}
	
	int mid = (l + r) / 2;
	treap_id[id[mid]] = o = new treap_node();

	treap_build(o -> ch[0], l, mid - 1);
	if (o -> ch[0] != treap_null)
		o -> ch[0] -> p = o;
	
	treap_build(o -> ch[1], mid + 1, r);
	if (o -> ch[1] != treap_null)
		o -> ch[1] -> p = o;
	
	o -> update();
}

void dfs(int x) {
	dfn[x] = ++tim;
	id[tim] = x;
	d[x] = d[pr[x]] + 1;

	for (int y : G[x])
		if (y != pr[x]) {
			pr[y] = x;

			dfs(y);

			lct_null[y].p = lct_null + x;
			lct_null[x].self_size += lct_null[y].tree_size;
		}
	
	lct_null[x].tree_size = lct_null[x].self_size;
}

int lca(int x, int y) {
	if (d[x] != d[y]) {
		if (d[x] < d[y])
			swap(x, y);
		
		int t = d[x] - d[y];
		for (int i = 0; i < 19; i++)
			if (t >> i & 1)
				x = f[i][x];
	}
	if (x == y)
		return x;
	
	for (int i = 18; ~i; i--)
		if (f[i][x] != f[i][y]) {
			x = f[i][x];
			y = f[i][y];
		}
	
	return f[0][x];
}

int main() {

	lct_null -> ch[0] = lct_null -> ch[1] = lct_null -> p = lct_null;
	lct_null -> self_size = lct_null -> tree_size = 0;
	treap_null -> ch[0] = treap_null -> ch[1] = treap_null -> p = treap_null;
	treap_null -> size = 0;
	sbt_null -> ch[0] = sbt_null -> ch[1] = sbt_null;
	sbt_null -> size = 0;

	int n, m;
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++)
		lct_init(lct_null + i);

	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);

		G[x].push_back(y);
		G[y].push_back(x);
	}

	dfs(1);

	for (int i = 1; i <= n; i++)
		f[0][i] = pr[i];
	
	for (int j = 1; j < 19; j++)
		for (int i = 1; i <= n; i++)
			f[j][i] = f[j - 1][f[j - 1][i]];
	
	treap_build(treap_root, 1, n);
	treap_root -> p = treap_null;

	int last = 0;

	while (m--) {
		int op;
		scanf("%d", &op);

		if (op == 1) {
			scanf("%d", &pr[++n]);
			pr[n] ^= last;

			d[n] = d[pr[n]] + 1;
			f[0][n] = pr[n];
			for (int j = 1; j < 19; j++)
				f[j][n] = f[j - 1][f[j - 1][n]];
			
			treap_id[n] = new treap_node();
			treap_id[n] -> ch[0] = treap_id[n] -> ch[1] = treap_id[n] -> p = treap_null;
			treap_node *last = treap_find(treap_rank(treap_id[pr[n]]) + lct_query(lct_null + pr[n]) - 1);
			treap_insert(treap_id[n], last);

			lct_init(lct_null + n);
			lct_link(lct_null + n, lct_null + pr[n]);
		}
		else if (op == 2) {
			int x, y, c, k;
			scanf("%d%d%d%d", &x, &y, &c, &k);
			x ^= last;
			y ^= last;
			c ^= last;
			k ^= last;

			int z = lca(x, y);
			treap_modify(treap_id[x], c, {-k, (long long)k * (d[x] + 1)});
			treap_modify(treap_id[y], c, {-k, (long long)k * (d[y] + 1)});
			treap_modify(treap_id[z], c, {2 * k, -k * (long long)(d[x] + d[y] + 2) + (long long)k * (d[x] + d[y] - 2 * d[z] + 1)});
		}
		else {
			int x, c;
			scanf("%d%d", &x, &c);
			x ^= last;
			c ^= last;

			int l = treap_rank(treap_id[x]), r = l + lct_query(lct_null + x) - 1;
			auto [a, b] = treap_query(treap_root, l, r, c);
			long long ans = a * d[x] + b;

			printf("%lld\n", ans);

			last = ans & 2147483647;
		}
	}

	return 0;
}