#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
const ll N = 2e5+5;
const ll LOG = 20;
ll n,m,q,u,v;
ll l,r,node,val;
ll upd,event;
bool ans;
ll depth[N],a[N];
ll anc[N][LOG];
vector<ll> adj[N];
set<pii> st,st2;
void dfs(ll x, ll y) {
anc[x][0] = y;
depth[x] = depth[y] + 1;
for(int i=1; i<LOG; i++) {
anc[x][i] = anc[anc[x][i-1]][i-1];
}
for(auto i : adj[x]) {
if(i == y) continue;
dfs(i,x);
}
}
ll lca(ll x, ll y) {
if(x == 0 || y == 0) return x+y;
if(x == n+1 || y == n+1) return x+y-(n+1);
if(depth[x] < depth[y]) swap(x,y);
for(int i=LOG-1; i>=0; i--) {
if(depth[anc[x][i]] >= depth[y]) {
x = anc[x][i];
}
}
if(x == y) return x;
for(int i=LOG-1; i>=0; i--) {
if(anc[x][i] != anc[y][i]) {
x = anc[x][i];
y = anc[y][i];
}
}
return anc[x][0];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for(int i=1; i<n; i++) {
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1,0);
for(int i=1; i<=m; i++) {
cin >> a[i];
st.insert({lca(a[i],a[i-1]),i});
st2.insert({a[i],i});
}
while(q--) {
cin >> event;
if(event == 1) {
cin >> upd >> val;
st.erase({lca(a[upd],a[upd-1]),upd});
st.erase({lca(a[upd],a[upd+1]),upd+1});
st2.erase({a[upd],upd});
a[upd] = val;
st.insert({lca(a[upd],a[upd-1]),upd});
st.insert({lca(a[upd],a[upd+1]),upd+1});
st2.insert({a[upd],upd});
}
else {
cin >> l >> r >> node;
pii var = {node,l};
auto temp = lb(st.begin(),st.end(),var);
auto temp2 = lb(st2.begin(),st2.end(),var);
if((*temp).fi == node && (*temp).se <= r && (*temp).se-1 >= l) {
cout << (*temp).se - 1 << " " << (*temp).se << endl;
}
else if((*temp2).fi == node && (*temp2).se <= r) {
cout << (*temp2).se << " " << (*temp2).se << endl;
}
else cout << "-1 -1" << endl;
}
}
}
/*
5 4 10
1 2
3 1
3 4
5 3
4 5 5 3
2 1 2 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8792 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
8792 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8792 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
8792 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8792 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
8792 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8792 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
8792 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
