#include <iostream>
#include <vector>
#include <set>
#define MAX_N 200000
#define MAX_M 200000
#define MAX_LG2N 18
using namespace std;
struct nodEuler {
int nod, depth;
bool operator < (const nodEuler &a) const {
return depth < a.depth;
}
};
struct solutie {
int lca, left, right;
bool operator < (const solutie &a) const {
if ( lca == a.lca ) {
if ( left == a.lca )
return right < a.right;
return left < a.left;
}
return lca < a.lca;
}
};
int eulerSize;
int poz[MAX_N], lg2[2 * MAX_N + 1], v[MAX_M];
nodEuler euler[2 * MAX_N], rmq[2 * MAX_N][MAX_LG2N + 1];
vector <int> muchii[MAX_N];
set <solutie> s;
void dfs( int parent, int nod, int depth ) {
int i;
euler[eulerSize] = { nod, depth };
poz[nod] = eulerSize;
eulerSize++;
for ( i = 0; i < muchii[nod].size(); i++ ) {
if ( muchii[nod][i] != parent ) {
dfs( nod, muchii[nod][i], depth + 1 );
euler[eulerSize] = { nod, depth };
poz[nod] = eulerSize;
eulerSize++;
}
}
}
void initLCA() {
int i, j;
dfs( -1, 0, 0 );
for ( i = 0; i < eulerSize; i++ )
rmq[i][0] = euler[i];
for ( j = 1; (1 << j) <= eulerSize; j++ ) {
for ( i = 0; i + (1 << j) <= eulerSize; i++ ) {
if ( rmq[i][j - 1] < rmq[i + (1 << (j - 1))][j - 1] )
rmq[i][j] = rmq[i][j - 1];
else
rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
}
}
for ( i = 2; i <= eulerSize; i++ )
lg2[i] = lg2[i / 2] + 1;
}
int queryLCA( int x, int y ) {
int s, d, aux, j;
s = poz[x];
d = poz[y];
if ( s > d ) {
aux = s;
s = d;
d = aux;
}
j = lg2[d - s + 1] ;
if ( rmq[s][j] < rmq[d - (1 << j) + 1][j] )
return rmq[s][j].nod;
return rmq[d - (1 << j) + 1][j].nod;
};
int main() {
int n, m, q, x, y, tip, l, r, p, i;
cin >> n >> m >> q;
for ( i = 0; i < n - 1; i++ ) {
cin >> x >> y;
x--;
y--;
muchii[x].push_back( y );
muchii[y].push_back( x );
}
initLCA();
for ( i = 0; i < m; i++ ) {
cin >> v[i];
v[i]--;
s.insert( { v[i], i, i } );
if( i > 0 )
s.insert( { queryLCA( v[i - 1], v[i] ), i - 1, i } );
}
for ( i = 0; i < q; i++ ) {
cin >> tip;
if ( tip == 1 ) {
cin >> p >> x;
p--;
x--;
s.erase( { v[p], p, p } );
if ( p > 0 )
s.erase( { queryLCA( v[p - 1], v[p] ), p - 1, p } );
if ( p < m - 1 )
s.erase( { queryLCA( v[p], v[p + 1] ), p, p + 1 } );
v[p] = x;
s.insert( { v[p], p, p } );
if ( p > 0 )
s.insert( { queryLCA( v[p - 1], v[p] ), p - 1, p } );
if ( p < m - 1 )
s.insert( { queryLCA( v[p], v[p + 1] ), p, p + 1 } );
} else {
cin >> l >> r >> x;
l--;
r--;
x--;
auto it = s.lower_bound( { x, l, 0 } );
if ( it != s.end() && it->lca == x && it->left >= l && it->right <= r )
cout << it->left + 1 << " " << it->right + 1 << "\n";
else
cout << "-1 -1\n";
}
}
return 0;
}
/**
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 'void dfs(int, int, int)':
treearray.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for ( i = 0; i < muchii[nod].size(); i++ ) {
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
5000 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 |
3 ms |
5000 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 |
3 ms |
5000 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 |
3 ms |
5000 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
