#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <chrono>
#include <numeric>
using namespace std;

class MinSegmentTree
{
	public:
		MinSegmentTree(const vector<int>& elements);
		int min_query(int l, int r);
		void update_value(int position, int new_value);
	private:
		vector<int> tree;
		int element_count;
};
class MaxSegmentTree
{
public:
	MaxSegmentTree(const vector<int>& elements);
	int max_query(int l, int r);
	void update_value(int position, int new_value);
private:
	vector<int> tree;
	int element_count;
};


vector<int> bfs(int node, const vector<int>& nodes_order, const vector<vector<int>>& tree)
{
	vector<bool> visited(nodes_order.size());
	vector<int> dist(nodes_order.size());

	queue<pair<int,int>> bfs_queue;
	bfs_queue.push({ node,0 });
	visited[node] = 1;
	while (!bfs_queue.empty())
	{
		int current_node = bfs_queue.front().first;
		int current_dist = bfs_queue.front().second;
		bfs_queue.pop();

		visited[current_node] = 1;
		for (int neighbor: tree[current_node])
		{
			if (!visited[neighbor])
			{
				bfs_queue.push({ neighbor, current_dist + 1 });
				dist[neighbor] = current_dist + 1;
			}
		}
	}
	return dist;
}

vector<int> solve_first_test_case(const vector<vector<int>>& tree, vector<int> nodes_order, const vector<vector<int>>& queries)
{
	int n = nodes_order.size();
	vector<vector<int>> all_distances(n, vector<int>(n));
	for (int i = 0; i < n; i++)
	{
		int node = nodes_order[i];
		all_distances[node] = bfs(node, nodes_order, tree);
	}

	int q = queries.size();
	vector<int> solutions;
	for (int i = 0; i < q; i++)
	{
		int type = queries[i][0];
		if (type == 1)
		{
			int a = queries[i][1], b = queries[i][2];
			a--; b--;
			swap(nodes_order[a], nodes_order[b]);
		}
		else
		{
			int l = queries[i][1], r = queries[i][2], x = queries[i][3];
			l--; r--; x--;
			int max_dist = 0;
			for (int i = l; i <= r; i++)
			{
				max_dist = max(max_dist, all_distances[x][nodes_order[i]]);
			}
			solutions.push_back(max_dist);
		}
	}
	return solutions;
}

vector<int> solve_second_test_case(const vector<vector<int>>& tree, vector<int> nodes_order, const vector<int>& degree, const vector<vector<int>>& queries)
{
	int start_node = -1;
	int n = degree.size();
	for (int i = 0; i < n; i++)
	{
		if (degree[i] == 1)
		{
			start_node = i;
			break;
		}
	}
	
	vector<int> new_labels(n);
	int prev_node = -1;
	int current_node = start_node;
	int current_label = 0;
	while (true)
	{
		new_labels[current_node] = current_label++;
		for (int neighbor: tree[current_node])
		{
			if (neighbor != prev_node)
			{
				prev_node = current_node;
				current_node = neighbor;
			}
		}
		if (degree[current_node] == 1)
		{
			new_labels[current_node] = current_label;
			break;
		}
	}

	for (int i = 0; i < n; i++)
	{
		nodes_order[i] = new_labels[nodes_order[i]];
	}
	auto min_seg_tree = MinSegmentTree(nodes_order);
	auto max_seg_tree = MaxSegmentTree(nodes_order);

	vector<int> solutions;
	for (int i = 0; i < queries.size(); i++)
	{
		int type = queries[i][0];
		if (type == 1)
		{
			int pos1 = queries[i][1], pos2 = queries[i][2];
			pos1--; pos2--;
			int val1 = nodes_order[pos1], val2 = nodes_order[pos2];
			min_seg_tree.update_value(pos1, val2);
			min_seg_tree.update_value(pos2, val1);
			max_seg_tree.update_value(pos1, val2);
			max_seg_tree.update_value(pos2, val1);
			swap(nodes_order[pos1], nodes_order[pos2]);
		}
		else
		{
			int l = queries[i][1], r = queries[i][2], x = queries[i][3];
			l--; x--;
			int min_val = min_seg_tree.min_query(l, r);
			int max_val = max_seg_tree.max_query(l, r);
			int labelx = new_labels[x];
			solutions.push_back(max(abs(labelx - min_val), abs(labelx - max_val)));
		}
	}
	return solutions;
}

vector<int> solve_third_test_case(const vector<vector<int>>& tree, vector<int> nodes_order, const vector<vector<int>>& queries)
{
	int src = 0;
	int n = nodes_order.size();
	vector<int> distances = bfs(src, nodes_order, tree);
	vector<int> ordered_distances(n);
	for (int i = 0; i < n; i++)
	{
		ordered_distances[i] = distances[nodes_order[i]];
	}
	auto max_seg_tree = MaxSegmentTree(ordered_distances);

	vector<int> solutions;
	for (int i = 0; i < queries.size(); i++)
	{
		int type = queries[i][0];
		if (type == 1)
		{
			int pos1 = queries[i][1], pos2 = queries[i][2];
			pos1--; pos2--;
			int val1 = ordered_distances[pos1], val2 = ordered_distances[pos2];
			max_seg_tree.update_value(pos1, val2);
			max_seg_tree.update_value(pos2, val1);
			swap(ordered_distances[pos1], ordered_distances[pos2]);
		}
		else
		{
			int l = queries[i][1], r = queries[i][2], x = queries[i][3];
			l--; x--;
			solutions.push_back(max_seg_tree.max_query(l, r));
		}
	}
	return solutions;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin >> n;
	vector<int> nodes_order(n);
	for (int i = 0; i < n; i++)
	{
		cin >> nodes_order[i];
		nodes_order[i]--;
	}
	vector<vector<int>> tree(n, vector<int>());
	vector<int> degree(n);
	for (int i = 0; i < n-1; i++)
	{
		int a, b; cin >> a >> b;
		a--; b--;
		tree[a].push_back(b);
		tree[b].push_back(a);
		degree[a]++;
		degree[b]++;
	}

	//vector<int> nodes_order(n);
	//iota(nodes_order.begin(), nodes_order.end(), 0);
	//random_shuffle(nodes_order.begin(), nodes_order.end());
	//auto tree = random_tree(n);

	int q; cin >> q;
	vector<vector<int>> queries(q,vector<int>());
	for (int i = 0; i < q; i++)
	{
		//int type = rand()%2 +1; 
		int type; cin >> type;
		queries[i].push_back(type);
		if (type == 1)
		{
			//int a = rand()%n+1, b = rand()%n+1;
			int a, b;
			cin >> a >> b;
			queries[i].push_back(a);
			queries[i].push_back(b);
		}
		else
		{
			//int l = rand()%n+1, r = rand()%n +1, x = 1; 
			int l, r, x;
			cin >> l >> r >> x;
			if (r < l)
			{
				swap(l, r);
			}
			queries[i].push_back(l);
			queries[i].push_back(r);
			queries[i].push_back(x);
		}
	}

	//auto sol1 = solve_first_test_case(tree, nodes_order, queries);
	//auto sol2 = solve_second_test_case(tree, nodes_order, degree, queries);
	//auto sol3 = solve_third_test_case(tree, nodes_order, queries);
	/*for (int i = 0; i < sol1.size(); i++)
	{
		if (sol1[i] != sol3[i])
		{
			cout << "wa";
		}
	}*/

	int max_deg = *max_element(degree.begin(), degree.end());
	vector<int> sol;
	if (n <= 4000 && q <= 4000)
	{
		sol = solve_first_test_case(tree, nodes_order, queries);
	}
	else if (max_deg <= 2)
	{
		sol = solve_second_test_case(tree, nodes_order, degree, queries);
	}
	else
	{
		sol = solve_third_test_case(tree, nodes_order, queries);
	}
	for (int i: sol)
	{
		cout << i << "\n";
	}

	return 0;
}


MinSegmentTree::MinSegmentTree(const vector<int>& elements)
{
	element_count = elements.size();
	tree = vector<int>(element_count * 2);
	copy(elements.begin(), elements.end(), tree.begin() + element_count);

	for (int i = element_count - 1; i > 0; i--)
		tree[i] = min(tree[2 * i], tree[2 * i + 1]);
}

int MinSegmentTree::min_query(int l, int r)
{
	l += element_count;
	r += element_count;
	int min_el = INT_MAX;
	while (l < r)
	{
		if (l % 2 == 1)
		{
			min_el = min(min_el, tree[l++]);
		}
		if (r % 2 == 1)
		{
			min_el = min(min_el, tree[--r]);
		}
		l /= 2;
		r /= 2;
	}
	return min_el;
}

void MinSegmentTree::update_value(int position, int new_value)
{
	position += element_count;
	tree[position] = new_value;
	for (int i = position / 2; i > 0; i /= 2)
		tree[i] = min(tree[2 * i], tree[2 * i + 1]);
}

MaxSegmentTree::MaxSegmentTree(const vector<int>& elements)
{
	element_count = elements.size();
	tree = vector<int>(element_count * 2);
	copy(elements.begin(), elements.end(), tree.begin() + element_count);

	for (int i = element_count - 1; i > 0; i--)
		tree[i] = max(tree[2 * i], tree[2 * i + 1]);
}

int MaxSegmentTree::max_query(int l, int r)
{
	l += element_count;
	r += element_count;
	int max_el = INT_MIN;
	while (l < r)
	{
		if (l % 2 == 1)
		{
			max_el = max(max_el, tree[l++]);
		}
		if (r % 2 == 1)
		{
			max_el = max(max_el, tree[--r]);
		}
		l /= 2;
		r /= 2;
	}
	return max_el;
}

void MaxSegmentTree::update_value(int position, int new_value)
{
	position += element_count;
	tree[position] = new_value;
	for (int i = position / 2; i > 0; i /= 2)
		tree[i] = max(tree[2 * i], tree[2 * i + 1]);
}