#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
using namespace std;
const long long oo = 1000000000000000000;
long long int sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
/*
ViHHiPuh
(( `'-""``""-'` ))
)-__-_.._-__-(
/ --- (o _ o) --- \
\ .-* ( .0. ) *-. /
_'-. ,_ '=' _, .-'_
/ `;#'#'# - #'#'#;` \
\_)) -----'#'----- ((_/
# --------- #
'# ------- ------ #'
/..-'# ------- #'-.\
_\...-\'# -- #'/-.../_
((____)- '#' -(____))
cout << fixed << setprecision(6) << x;
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen ( "sum.in", "r", stdin )
*/
int x, y, l, r, a[ 200001 ], type, par[ 200001 ][ 21 ], lg = 20;
vector <int> v[ 200001 ], vv;
int tin[ 200001 ], tout[ 200001 ], tmr, d[ 200001 ], t[ 800001 ];
void dfs( int u, int pr = 1 ) {
par[ u ][ 0 ] = pr;
vv.push_back( u );
tin[ u ] = ++tmr;
for ( int i = 1; i <= lg; i ++ )
par[ u ][ i ] = par[ par[ u ][ i - 1 ] ][ i - 1 ];
for ( auto to : v[ u ] ) {
if ( to != pr ) {
d[ to ] = d[ u ] + 1;
dfs( to, u );
}
}
tout[ u ] = tmr;
}
bool ok( int a, int b ) {
return ( tin[ a ] <= tin[ b ] && tout[ a ] >= tout[ b ] );
}
int lca( int a, int b ) {
if ( ok( a, b ) )
return a;
if ( ok( b, a ) )
return b;
for ( int i = lg; i >= 0; i -- ) {
if ( !ok( par[ a ][ i ], b ) )
a = par[ a ][ i ];
}
return par[ a ][ 0 ];
}
void build( int v, int tl, int tr ) {
if ( tl == tr ) {
t[ v ] = a[ tl ];
return;
}
int mid = ( tl + tr ) / 2;
build( v + v, tl, mid );
build( v + v + 1, mid + 1, tr );
t[ v ] = lca( t[ v + v ], t[ v + v + 1 ] );
}
void upd( int v, int tl, int tr, int pos, int x ) {
if ( tl > pos || tr < pos )
return;
if ( tl == tr ) {
t[ v ] = x;
return;
}
int mid = ( tl + tr ) / 2;
upd( v + v, tl, mid, pos, x );
upd( v + v + 1, mid + 1, tr, pos, x );
t[ v ] = lca( t[ v + v ], t[ v + v + 1 ] );
}
void gett( int v, int tl, int tr, int l, int r ) {
if ( tl > r || tr < l )
return;
if ( tl >= l && tr <= r ) {
if ( !num )
num = t[ v ];
else
num = lca( num, t[ v ] );
return;
}
int mid = ( tl + tr ) / 2;
gett( v + v, tl, mid ,l ,r );
gett( v + v + 1, mid + 1, tr, l, r );
}
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
srand( time(0) );
int n, m, q;
cin >> n >> m >> q;
for ( int i = 1; i < n; i ++ ) {
cin >> x >> y;
v[ x ].push_back( y );
v[ y ].push_back( x );
}
for ( int i = 1; i <= m; i ++ ) {
cin >> a[ i ];
}
dfs( 1 );
build( 1, 1, m );
int L, R, ll, rr;
while ( q -- ) {
cin >> type >> l >> r;
if ( type == 2 ) {
cin >> x;
sum = 100;
while ( sum -- ) {
R = rand() % ( r - l + 1 ) + l;
L = rand() % ( r - l + 1 ) + l;
if ( L > R )
swap( L, R );
num = 0;
gett( 1, 1, m, L, R );
if ( num == x )
break;
}
if ( num != x )
cout << "-1 -1\n";
else
cout << L << " " << R << "\n";
}
else {
upd( 1, 1, m, l, r );
}
}
}
/*
CX
1 1 3
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: In function 'int main()':
treearray.cpp:135:12: warning: unused variable 'll' [-Wunused-variable]
135 | int L, R, ll, rr;
| ^~
treearray.cpp:135:16: warning: unused variable 'rr' [-Wunused-variable]
135 | int L, R, ll, rr;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
n=5 |
| 2 |
Incorrect |
5 ms |
4940 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
n=5 |
| 2 |
Incorrect |
5 ms |
4940 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
n=5 |
| 2 |
Incorrect |
5 ms |
4940 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
n=5 |
| 2 |
Incorrect |
5 ms |
4940 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
