This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.IntStream;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.stream.IntStream.*;
/********************************************/
public class treearray {
public static void main(String[] args) throws IOException {
new Solution().run();
}
}
/********************************************/
class Solution {
final FastScanner scanner = new FastScanner();
final PrintWriter out = new PrintWriter(System.out);
final int mod = (int) 1e9+7;
final int[] dx = {1, 0, -1, 0};
final int[] dy = {0, 1, 0, -1};
int maxn = (int) 3e5+10;
int n, m, q;
int[] a, d;
int[][] up;
TreeSet<Integer>[] s, t;
void solve() throws IOException {
n = scanner.nextInt(); m = scanner.nextInt(); q = scanner.nextInt();
init(n); up = new int[20][n+1]; a = new int[m+1]; d = new int[n+1];
s = new TreeSet[n+1]; t = new TreeSet[n+1];
for (int i = 1; i<n; i++) {
int x = scanner.nextInt(), y = scanner.nextInt();
g[x].add(y); g[y].add(x);
}
for (int i = 1; i<=m; i++) {
a[i] = scanner.nextInt();
}
for (int i = 1; i<=n; i++) {
s[i] = new TreeSet<>();
t[i] = new TreeSet<>();
}
dfs(1, 1);
for (int i = 1; i<=m; i++) s[a[i]].add(i);
for (int i = 2; i<=m; i++) t[lca(a[i], a[i-1])].add(i);
for(int i = 1; i <= n; i++) {
s[i].add(mod);
t[i].add(mod);
}
for(int i = 0, type, l, r, x; i < q; i++){
type = scanner.nextInt();
if (type == 1){
l = scanner.nextInt(); x = scanner.nextInt();
s[a[l]].remove(l);
if(l > 1) t[lca(a[l], a[l-1])].remove(l);
if(l < m) t[lca(a[l], a[l+1])].remove(l+1);
a[l] = x;
s[a[l]].add(l);
if(l > 1) t[lca(a[l], a[l-1])].add(l);
if(l < m) t[lca(a[l], a[l+1])].add(l+1);
} else {
l = scanner.nextInt(); r = scanner.nextInt(); x = scanner.nextInt();
var d = s[x].ceiling(l);
var e = t[x].ceiling(l+1);
if (d!=null && d <= r){
out.println(d+" "+d);
} else if(e!=null && e <= r){
out.println((e-1)+" "+e);
} else{
out.println("-1 -1");
}
}
}
}
void dfs(int v, int pr) {
up[0][v] = pr;
for(int i = 1; i < 19; i++){
up[i][v] = up[i-1][up[i-1][v]];
}
d[v] = d[pr] + 1;
for(var to : g[v]) {
if(to == pr) continue;
dfs(to, v);
}
}
int lca(int u, int v) {
if(d[u] < d[v]) {
int temp = u;
u = v;
v = temp;
}
for(int i = 18; i >= 0; i--){
if(d[u] - (1<<i) >= d[v]) {
u = up[i][u];
}
}
if(u == v) return u;
for(int i = 18; i >= 0; i--){
if(up[i][u] != up[i][v]) {
u = up[i][u];
v = up[i][v];
}
}
return up[0][v];
}
List<Integer>[] g;
boolean[] was;
void init(int n) {
g = new ArrayList[n+1];
was = new boolean[n+1];
for (int i = 0; i<=n; i++) {
g[i] = new ArrayList<>();
}
}
void run() throws IOException {
int t = 1;
while (t-->0) {
solve();
}
out.flush();
}
}
class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int nextInt() throws IOException {
int x = 0, sign = 1;
char c = (char) br.read();
while ((c < '0' || c > '9') && c != '-') {
c = (char) br.read();
}
if (c == '-') {
sign = -1;
c = (char) br.read();
}
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c & 15);
c = (char) br.read();
}
return sign * x;
}
long nextLong() throws IOException {
long x = 0, sign = 1;
char c = (char) br.read();
while ((c < '0' || c > '9') && c != '-') {
c = (char) br.read();
}
if (c == '-') {
sign = -1;
c = (char) br.read();
}
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c & 15);
c = (char) br.read();
}
return sign * x;
}
String next() throws IOException {
StringBuilder sb = new StringBuilder();
char c = (char) br.read();
while (c == ' ' || c == '\n' || c == '\r') {
c = (char) br.read();
}
while (c != ' ' && c != '\n' && c != '\r') {
sb.append(c);
c = (char) br.read();
}
return sb.toString();
}
int[] readArray(int n) throws IOException {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
long[] readLong(int n) throws IOException {
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
}
Compilation message (stderr)
treearray.cpp:1:1: error: 'import' does not name a type
1 | import java.io.*;
| ^~~~~~
treearray.cpp:2:1: error: 'import' does not name a type
2 | import java.math.BigInteger;
| ^~~~~~
treearray.cpp:3:1: error: 'import' does not name a type
3 | import java.util.*;
| ^~~~~~
treearray.cpp:4:1: error: 'import' does not name a type
4 | import java.util.stream.IntStream;
| ^~~~~~
treearray.cpp:6:1: error: 'import' does not name a type
6 | import static java.lang.Math.*;
| ^~~~~~
treearray.cpp:7:1: error: 'import' does not name a type
7 | import static java.util.Arrays.*;
| ^~~~~~
treearray.cpp:8:1: error: 'import' does not name a type
8 | import static java.util.stream.IntStream.*;
| ^~~~~~
treearray.cpp:11:1: error: expected unqualified-id before 'public'
11 | public class treearray {
| ^~~~~~
treearray.cpp:19:2: error: 'final' does not name a type
19 | final FastScanner scanner = new FastScanner();
| ^~~~~
treearray.cpp:20:2: error: 'final' does not name a type
20 | final PrintWriter out = new PrintWriter(System.out);
| ^~~~~
treearray.cpp:21:2: error: 'final' does not name a type
21 | final int mod = (int) 1e9+7;
| ^~~~~
treearray.cpp:22:2: error: 'final' does not name a type
22 | final int[] dx = {1, 0, -1, 0};
| ^~~~~
treearray.cpp:23:2: error: 'final' does not name a type
23 | final int[] dy = {0, 1, 0, -1};
| ^~~~~
treearray.cpp:26:5: error: expected unqualified-id before '[' token
26 | int[] a, d;
| ^
treearray.cpp:27:5: error: expected unqualified-id before '[' token
27 | int[][] up;
| ^
treearray.cpp:28:2: error: 'TreeSet' does not name a type
28 | TreeSet<Integer>[] s, t;
| ^~~~~~~
treearray.cpp:30:13: error: expected ';' at end of member declaration
30 | void solve() throws IOException {
| ^
| ;
treearray.cpp:30:15: error: 'throws' does not name a type
30 | void solve() throws IOException {
| ^~~~~~
treearray.cpp:111:2: error: 'List' does not name a type
111 | List<Integer>[] g;
| ^~~~
treearray.cpp:112:2: error: 'boolean' does not name a type; did you mean 'bool'?
112 | boolean[] was;
| ^~~~~~~
| bool
treearray.cpp:122:11: error: expected ';' at end of member declaration
122 | void run() throws IOException {
| ^
| ;
treearray.cpp:122:13: error: 'throws' does not name a type
122 | void run() throws IOException {
| ^~~~~~
treearray.cpp:129:2: error: expected ';' after class definition
129 | }
| ^
| ;
treearray.cpp: In member function 'void Solution::dfs(int, int)':
treearray.cpp:79:3: error: 'up' was not declared in this scope
79 | up[0][v] = pr;
| ^~
treearray.cpp:83:3: error: 'd' was not declared in this scope
83 | d[v] = d[pr] + 1;
| ^
treearray.cpp:84:7: error: 'var' was not declared in this scope
84 | for(var to : g[v]) {
| ^~~
treearray.cpp:88:2: error: expected primary-expression before '}' token
88 | }
| ^
treearray.cpp:87:4: error: expected ';' before '}' token
87 | }
| ^
| ;
88 | }
| ~
treearray.cpp:88:2: error: expected primary-expression before '}' token
88 | }
| ^
treearray.cpp:87:4: error: expected ')' before '}' token
87 | }
| ^
| )
88 | }
| ~
treearray.cpp:84:6: note: to match this '('
84 | for(var to : g[v]) {
| ^
treearray.cpp:88:2: error: expected primary-expression before '}' token
88 | }
| ^
treearray.cpp: In member function 'int Solution::lca(int, int)':
treearray.cpp:91:6: error: 'd' was not declared in this scope
91 | if(d[u] < d[v]) {
| ^
treearray.cpp:97:7: error: 'd' was not declared in this scope
97 | if(d[u] - (1<<i) >= d[v]) {
| ^
treearray.cpp:98:9: error: 'up' was not declared in this scope; did you mean 'u'?
98 | u = up[i][u];
| ^~
| u
treearray.cpp:103:7: error: 'up' was not declared in this scope; did you mean 'u'?
103 | if(up[i][u] != up[i][v]) {
| ^~
| u
treearray.cpp:108:10: error: 'up' was not declared in this scope; did you mean 'u'?
108 | return up[0][v];
| ^~
| u
treearray.cpp: In member function 'void Solution::init(int)':
treearray.cpp:115:3: error: 'g' was not declared in this scope
115 | g = new ArrayList[n+1];
| ^
treearray.cpp:115:11: error: 'ArrayList' does not name a type
115 | g = new ArrayList[n+1];
| ^~~~~~~~~
treearray.cpp:116:3: error: 'was' was not declared in this scope
116 | was = new boolean[n+1];
| ^~~
treearray.cpp:116:13: error: 'boolean' does not name a type; did you mean 'bool'?
116 | was = new boolean[n+1];
| ^~~~~~~
| bool
treearray.cpp:118:15: error: 'ArrayList' does not name a type
118 | g[i] = new ArrayList<>();
| ^~~~~~~~~
treearray.cpp:118:25: error: expected primary-expression before '>' token
118 | g[i] = new ArrayList<>();
| ^
treearray.cpp:118:27: error: expected primary-expression before ')' token
118 | g[i] = new ArrayList<>();
| ^
treearray.cpp: At global scope:
treearray.cpp:132:2: error: 'BufferedReader' does not name a type
132 | BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
| ^~~~~~~~~~~~~~
treearray.cpp:134:14: error: expected ';' at end of member declaration
134 | int nextInt() throws IOException {
| ^
| ;
treearray.cpp:134:16: error: 'throws' does not name a type
134 | int nextInt() throws IOException {
| ^~~~~~
treearray.cpp:152:16: error: expected ';' at end of member declaration
152 | long nextLong() throws IOException {
| ^
| ;
treearray.cpp:152:18: error: 'throws' does not name a type
152 | long nextLong() throws IOException {
| ^~~~~~
treearray.cpp:170:2: error: 'String' does not name a type
170 | String next() throws IOException {
| ^~~~~~
treearray.cpp:183:5: error: expected unqualified-id before '[' token
183 | int[] readArray(int n) throws IOException {
| ^
treearray.cpp:189:6: error: expected unqualified-id before '[' token
189 | long[] readLong(int n) throws IOException {
| ^
treearray.cpp:194:2: error: expected ';' after class definition
194 | }
| ^
| ;