#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int sz, n, m, k;
vector<int> edges[N];
int tin[N], tout[N];
int up[N][19];
int timer;
int depth[N];
void dfs(int u, int p, int d=0){
tin[u] = timer++;
depth[u] = d;
up[u][0] = p;
for(int i=1;i<19;i++)up[u][i] = up[up[u][i-1]][i-1];
for(auto v : edges[u]){
if(v != p){
dfs(v, u,d+1);
}
}tout[u] = timer++;
}
bool isancestor(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(isancestor(u,v))return u;
if(isancestor(v,u))return v;
for(int i=18;i>=0;i--){
if(!isancestor(up[u][i], v))u = up[u][i];
}return up[u][0];
}
int t[N*4];
void update(int p, int val){
for(t[p+=sz] = val; p>1; p>>=1)t[p>>1] = lca(t[p], t[p^1]);
}
int rangelca(int l, int r){
int ans = 0;
for(l+=sz,r+=sz;l<=r;l>>=1,r>>=1){
if(l%2 == 1){
if(ans == 0)ans = t[l++];
else ans = lca(ans, t[l++]);
}if(r%2==0){
if(ans == 0)ans = t[r--];
else ans = lca(ans, t[r--]);
}
}return ans;
}
/*int lef(int l, int r, int L, int R, int node, int v){
if(L >= r || R <= l)return -1;
if(depth[t[node]] > depth[v])return -1;
int mid = (L+R)/2;
if(L >= l && R <= r){
}else {
return max(lef(l,r,L, mid, node*2, v), lef(l,r, mid, R, node*2+1, v));
}
}*/
void solve(int test_case){
int i, j, q;
cin >> n >> m >> q;
for(i=1;i<n;i++){
int u, v;
cin >> u >> v;
edges[u].pb(v);
edges[v].pb(u);
}dfs(1,1);
sz=1;
while(sz < n)sz<<=1;
for(i=0;i<m;i++){
cin >> t[i+sz];
}for(i=sz-1;i>0;i--){
t[i] = lca(t[i*2], t[i*2+1]);
}
while(q--){
int type;
cin >> type;
if(type == 1){
int pos, val;
cin >> pos >> val;
update(pos-1, val);
}else {
int l, r, v;
cin >> l >> r >> v;
l--,r--;
//int ans = lef(l, r, 0, sz, 1, u);
int L=l, R=l;
while(R <= r){
while(R+1 <= r && depth[lca(v, rangelca(L,R+1))] <= depth[v])R++;
while(L+1 <=R && depth[lca(v, rangelca(L,R))] > depth[v])L++;
R++;
}R--;
while(R-1 >= L && depth[lca(v, rangelca(L,R))] < depth[v])R--;
while(L+1 <=R && depth[lca(v, rangelca(L,R))] > depth[v])L++;
// cout << rangelca(L, R) << '\n';
if(rangelca(L,R) == v)cout << L+1 << ' ' << R+1 << '\n';
else cout << "-1 -1\n";
}
}
return;
}
signed main(){
FASTIO;
#define MULTITEST 0
#if MULTITEST
int ___T;
cin >> ___T;
for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
Compilation message
treearray.cpp: In function 'void solve(long long int)':
treearray.cpp:69:9: warning: unused variable 'j' [-Wunused-variable]
69 | int i, j, q;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
n=5 |
| 2 |
Incorrect |
4 ms |
5100 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
n=5 |
| 2 |
Incorrect |
4 ms |
5100 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
n=5 |
| 2 |
Incorrect |
4 ms |
5100 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
n=5 |
| 2 |
Incorrect |
4 ms |
5100 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
