#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+5;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e9;
const ll mod=1e9+7;
int n,m,q,up[maxn][19],in[maxn],out[maxn],a[maxn],Time;
set<pii> L[maxn];
vector<int> adj[maxn];
void dfs(int u,int pre)
{
in[u]=++Time;
up[u][0]=pre;
for1(i,1,18)
{
up[u][i]=up[up[u][i-1]][i-1];
}
for(int v: adj[u])
{
if (v==pre) continue;
dfs(v,u);
}
out[u]=Time;
}
bool chk(int u,int v)
{
return (in[u]<=in[v] && out[v]<=out[u]);
}
int lca(int u,int v)
{
if (chk(u,v)) return u;
if (chk(v,u)) return v;
for2(i,18,0)
{
if (!chk(up[u][i],v)) u=up[u][i];
}
return up[u][0];
}
void sol()
{
cin >> n>>m>>q;
for1(i,2,n)
{
int u,v; cin >> u>> v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1,1);
//cerr<< chk(4,5)<<" wtf\n";
for1(i,1,m)
{
cin >> a[i];
L[a[i]].insert({i,i});
}
for1(i,1,m-1)
{
L[lca(a[i],a[i+1])].insert({i,i+1});
}
for1(i,1,q)
{
//cerr<< i<<'\n';
int type; cin >> type;
if (type==1)
{
int pos,u;cin >> pos>>u;
L[a[pos]].erase({pos,pos});
L[u].insert({pos,pos});
if (pos>1)
{
L[lca(a[pos],a[pos-1])].erase({pos-1,pos});
L[lca(u,a[pos-1])].insert({pos-1,pos});
}
if (pos<m)
{
L[lca(a[pos],a[pos+1])].erase({pos,pos+1});
L[lca(u,a[pos+1])].insert({pos,pos+1});
}
a[i]=u;
}
else
{
int l,r,u;cin >> l>> r>>u;
auto it=L[u].lower_bound({l,l});
if (it!=L[u].end() && it->se <=r) cout << it->fi << ' '<<it->se<<'\n';
else cout << -1 << ' '<<-1<<'\n';
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("GROUPDIV.inp","r",stdin);
// freopen("GROUPDIV.out","w",stdout);
int t=1;//cin >> t;
while (t--)
{
sol();
}
}
/*
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
5 4 1
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14416 KB |
n=5 |
| 2 |
Incorrect |
9 ms |
14420 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14416 KB |
n=5 |
| 2 |
Incorrect |
9 ms |
14420 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14416 KB |
n=5 |
| 2 |
Incorrect |
9 ms |
14420 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14416 KB |
n=5 |
| 2 |
Incorrect |
9 ms |
14420 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
