#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fi first
#define se second
#define ll long long
using namespace std;
const int N = 1e6 + 7;
const int mod = 1e9 + 7;
int n,m,q;
int l=1;
int cnt;
int a[N];
int tin[N];
int tout[N];
set < pair < int , int > > s[N];
vector < int > v[N];
vector < int > up[N];
void dfs( int x , int p )
{
tin[x] = ++cnt;
up[x][0] = p;
for( int i = 1; i <= l; i++ ){
up[x][i] = up[up[x][i - 1]][i - 1];
}
for( auto y : v[x] ){
if( y != p ){
dfs(y , x);
}
}
tout[x] = cnt;
}
bool upper( int x , int y )
{
return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}
int lca( int x , int y )
{
if( upper(x , y) )return x;
if( upper(y , x) )return y;
for( int i = l; i >= 0; i-- ){
if( !upper(up[x][i] , y) ){
x = up[x][i];
}
}
return up[x][0];
}
void solve()
{
cin >> n >> m >> q;
while( (1 << l) <= n )l++;
for( int i = 0; i <= n; i++ ){
up[i].resize(l + 10);
}
for( int i = 1; i < n; i++ ){
int x,y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1 , 1);
for( int i = 1; i <= m; i++ ){
cin >> a[i];
s[a[i]].insert({i , i});
if( i > 1 )s[lca(a[i - 1] , a[i])].insert({i - 1, i});
}
for( int i = 1; i <= q; i++ ){
int gh;
cin >> gh;
if( gh == 1 ){
int p , vv;
cin >> p >> vv;
if( p > 1 )s[lca(a[p - 1] , a[p])].erase({p - 1 , p});
if( p < m )s[lca(a[p] , a[p + 1])].erase({p , p + 1});
a[p] = vv;
s[a[p]].insert({p , p});
if( p > 1 )s[lca(a[p - 1] , a[p])].insert({p - 1 , p});
if( p < m )s[lca(a[p] , a[p + 1])].insert({p , p + 1});
}
else{
int l , r , vv;
int lg = -1 , rg = -1;
cin >> l >> r >> vv;
auto it = s[vv].lower_bound({l , 0});
if( it != s[vv].end() ){
if( it->se <= r ){
lg = it->fi;
rg = it->se;
}
}
cout << lg << " " << rg << "\n";
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen( "input.txt" , "r" , stdin );
//freopen( "output.txt" , "w" , stdout );
int t = 1;//cin >> t;
while( t-- ){
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
94328 KB |
n=5 |
2 |
Incorrect |
86 ms |
94328 KB |
Wrong range. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
94328 KB |
n=5 |
2 |
Incorrect |
86 ms |
94328 KB |
Wrong range. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
94328 KB |
n=5 |
2 |
Incorrect |
86 ms |
94328 KB |
Wrong range. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
94328 KB |
n=5 |
2 |
Incorrect |
86 ms |
94328 KB |
Wrong range. |
3 |
Halted |
0 ms |
0 KB |
- |