#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const int lg;
int n, m, q, timer, t[N * 4], x[N], lvl[N], tin[N], tout[N], used[N], up[N][lg + 5];
vector < int > g[N];
int dfs(int v, int p = 1, int h = 0) {
used[v] = 1;
up[v][0] = p;
tin[v] = ++timer;
lvl[v] = h;
for (int i = 1; i <= lg; ++i) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
for (int to : g[v]) {
if (!used[to]) {
dfs(to, v, h + 1);
}
}
tout[v] = ++timer;
}
int lca(int a, int b) {
if (lvl[a] < lvl[b])
swap(a, b);
if (tin[b] <= tin[a] && tout[b] >= tout[a])
return b;
for (int i = lg; i >= 0; --i) {
if (lvl[up[a][i]] >= lvl[b]) {
a = up[a][i];
}
}
if (a == b)
return a;
for (int i = lg; i >= 0; --i) {
if (up[a][i] != up[b][i]) {
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
inline void build(int v, int tl, int tr) {
if (tl == tr) {
t[v] = x[tl];
return;
}
int tm = tl + tr >> 1;
build(v + v, tl, tm);
build(v + v + 1, tm + 1, tr);
t[v] = lca(t[v + v], t[v + v + 1]);
}
inline void upd(int v, int tl, int tr, int pos, int x) {
if (tl == tr) {
t[v] = x;
return;
}
int tm = tl + tr >> 1;
if (pos <= tm)
upd(v + v, tl, tm, pos, x);
else
upd(v + v + 1, tm + 1, tr, pos, x);
t[v] = lca(t[v + v], t[v + v + 1]);
}
int get(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return -1;
if (tl >= l && tr <= r)
return t[v];
int tm = tl + tr >> 1;
int lv = get(v + v, tl, tm, l, r);
int rv = get(v + v + 1, tm + 1, tr, l, r);
if (lv == -1)
lv = rv;
else if (rv == -1)
rv = lv;
return lca(lv, rv);
}
int getq(int l, int r) {
return get(1, 1, m, l, r);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
lg = log2(n) + 1;
for (int i = 1; i < n; ++i) {
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs(1);
for (int i = 1; i <= m; ++i) {
cin >> x[i];
}
build(1, 1, m);
while (q--) {
int ll = -1, rr = -1, l, r, type;
cin >> type >> l >> r;
if (type == 1) {
upd(1, 1, m, l, r);
} else {
int v;
cin >> v;
for (int a = l; a <= r; ++a) {
for (int b = a; b <= r; ++b) {
if (getq(a, b) == v) {
ll = a;
rr = b;
break;
}
}
if (max(ll, rr) != -1)
break;
}
cout << ll << " " << rr << "\n";
}
}
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/
Compilation message
treearray.cpp:13:11: error: uninitialized const 'lg' [-fpermissive]
const int lg;
^~
treearray.cpp:15:83: error: array bound is not an integer constant before ']' token
int n, m, q, timer, t[N * 4], x[N], lvl[N], tin[N], tout[N], used[N], up[N][lg + 5];
^
treearray.cpp: In function 'int dfs(int, int, int)':
treearray.cpp:21:5: error: 'up' was not declared in this scope
up[v][0] = p;
^~
treearray.cpp:21:5: note: suggested alternative: 'p'
up[v][0] = p;
^~
p
treearray.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
treearray.cpp: In function 'int lca(int, int)':
treearray.cpp:41:17: error: 'up' was not declared in this scope
if (lvl[up[a][i]] >= lvl[b]) {
^~
treearray.cpp:48:13: error: 'up' was not declared in this scope
if (up[a][i] != up[b][i]) {
^~
treearray.cpp:53:12: error: 'up' was not declared in this scope
return up[a][0];
^~
treearray.cpp: In function 'void build(int, int, int)':
treearray.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
~~~^~~~
treearray.cpp: In function 'void upd(int, int, int, int, int)':
treearray.cpp:72:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
~~~^~~~
treearray.cpp: In function 'int get(int, int, int, int, int)':
treearray.cpp:85:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int tm = tl + tr >> 1;
~~~^~~~
treearray.cpp: In function 'int main()':
treearray.cpp:103:20: error: assignment of read-only variable 'lg'
lg = log2(n) + 1;
^
