//#pragma GCC optomize ("Ofast")
//#pragma GCC optomize ("unroll-loops")
//#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define sz size
#define cl clear
#define ins insert
#define ers erase
#define pii pair < int , int >
#define pll pair< long long , long long >
#define all(x) x.begin() , x.end()
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define tostr(x) to_string(x)
#define tonum(s) atoi(s.c_str())
#define seon(x) setprecision(x)
#define bpop(x) __builtin_popcount(x)
#define deb(x) cerr << #x << " = " << x << endl;
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
const double PI = 3.14159265;
const ll N = 2e5+5;
const ll mod = 1e9+7;
const ll inf = 1e9;
const ll INF = 1e18;
using namespace std;
int n , m , q , a[N];
int dep[N] , up[N][20] ;
vector<int> g[N];
set<int> st1[N];
set<pii> st;
void dfs(int v, int p){
dep[v] = dep[p]+1;
up[v][0] = p;
for(int i = 1; i < 20; i++){
up[v][i] = up[up[v][i-1]][i-1];
}
for(int to : g[v]){
if(to == p) continue;
dfs(to , v);
}
}
int lca(int a , int b){
if(dep[a] > dep[b]) swap(a , b);
for(int i = 19; i >= 0; i--){
if(dep[up[b][i]] >= dep[a]){
b = up[b][i];
}
}
if(b == a) return a;
for(int i = 19; i >= 0; i--){
if(up[b][i] != up[a][i]){
b = up[b][i];
a = up[a][i];
}
}
return up[b][0];
}
void solve(){
cin >> n >> m >> q;
for(int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
dfs(1 , 0);
for(int i = 1; i <= m; i++) {
cin >> a[i];
if(i) st.ins({lca(a[i] , a[i-1]) , i-1});
st1[a[i]].ins(i);
}
while(q--){
int tp;
cin >> tp;
if(tp == 1){
int pos , v;
cin >> pos >> v;
st1[a[pos]].ers(pos);
if(pos-1 >= 1) st.ers({lca(a[pos] , a[pos-1]) , pos-1});
if(pos+1 <= m) st.ers({lca(a[pos] , a[pos+1]) , pos});
a[pos] = v;
st1[a[pos]].ins(pos);
if(pos-1 >= 1) st.ers({lca(a[pos] , a[pos-1]) , pos-1});
if(pos+1 <= m) st.ers({lca(a[pos] , a[pos+1]) , pos});
} else {
int l , r , v;
cin >> l >> r >> v;
auto it = st1[v].lower_bound(l);
if(it != st1[v].end()){
if(*it <= r){
cout << *it <<" " << *it << "\n";
continue;
}
}
auto it1 = st.lower_bound({v , l});
if(it1 != st.end()){
pii a = *it1;
if(a.F == v && a.S <= r-1){
cout << a.S <<" " << a.S+1 << "\n";
continue;
}
}
cout << -1 << " " << -1 <<"\n";
}
}
}
signed main(){
ios;
solve();
return 0;
}
/*
11
1 2
2 3
2 4
1 5
5 6
6 7
6 8
5 9
9 10
9 11
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
n=5 |
| 2 |
Correct |
8 ms |
14420 KB |
n=100 |
| 3 |
Correct |
7 ms |
14420 KB |
n=100 |
| 4 |
Incorrect |
7 ms |
14420 KB |
Jury has the answer but participant has not |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
n=5 |
| 2 |
Correct |
8 ms |
14420 KB |
n=100 |
| 3 |
Correct |
7 ms |
14420 KB |
n=100 |
| 4 |
Incorrect |
7 ms |
14420 KB |
Jury has the answer but participant has not |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
n=5 |
| 2 |
Correct |
8 ms |
14420 KB |
n=100 |
| 3 |
Correct |
7 ms |
14420 KB |
n=100 |
| 4 |
Incorrect |
7 ms |
14420 KB |
Jury has the answer but participant has not |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14420 KB |
n=5 |
| 2 |
Correct |
8 ms |
14420 KB |
n=100 |
| 3 |
Correct |
7 ms |
14420 KB |
n=100 |
| 4 |
Incorrect |
7 ms |
14420 KB |
Jury has the answer but participant has not |
| 5 |
Halted |
0 ms |
0 KB |
- |
