#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define db double
using namespace std;
int n,m,q;
int a[200001];
vector<int> g[200001];
int A[200001][20];
int p[200001];
int tin[200001],tout[200001];
int timer=0;
int lcas[200001];
set<int> s[200001];
set<int> s2[200001];
set<int>::iterator it;
void dfs(int v,int e){
p[v]=e;
tin[v]=++timer;
for(int i:g[v]){
if(i!=e){
dfs(i,v);
}
}
tout[v]=++timer;
}
void prepare(){
for(int i=1;i<=n;i++){
A[i][0]=p[i];
for(int k=1;k<=20;k++){
A[i][k]=-1;
}
}
for(int k=1;k<=20;k++){
for(int i=1;i<=n;i++){
if(A[i][k]==-1){
if(A[i][k-1]!=-1){
A[i][k]=A[A[i][k-1]][k-1];
}
}
}
}
}
bool isancestor(int u,int v){
return (tin[u]<=tin[v]&&tout[u]>=tout[v]);
}
int lca(int x,int y){
if(isancestor(x,y))
return x;
if(isancestor(y,x))
return y;
for(int k=20;k>=0;k--){
if(A[x][k]==-1)
continue;
if(!isancestor(A[x][k],y)){
x=A[x][k];
}
}
return p[x];
}
int main(){
cin>>n>>m>>q;
for(int k=1;k<n;k++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int k=1;k<=m;k++){
cin>>a[k];
s2[a[k]].insert(k);
}
dfs(1,-1);
prepare();
for(int k=1;k<m;k++){
int f=lca(a[k],a[k+1]);
lcas[k]=f;
s[f].insert(k);
}
while(q--){
int ind;
cin>>ind;
if(ind==2){
int x,y,z;
cin>>x>>y>>z;
it=s2[z].lower_bound(x);
if(it!=s2[z].end()){
int f1=*it;
if(f1<=y){
cout<<f1<<' '<<f1<<"\n";
continue;
}
}
it=s[z].lower_bound(x);
if(it==s[z].end()){
cout<<-1<<' '<<-1<<"\n";
continue;
}
int f=*it;
if(f>(y-1)){
cout<<-1<<' '<<-1<<"\n";
continue;
}
cout<<f<<' '<<f+1<<"\n";
}
else{
int x,y;
cin>>x>>y;
s2[a[x]].erase(x);
s2[y].insert(x);
a[x]=y;
if(x>1){
int prev=lcas[x-1];
s[prev].erase(x-1);
int cur=lca(a[x-1],a[x]);
s[cur].insert(x-1);
lcas[x-1]=cur;
}
if(x<m){
int prev=lcas[x];
s[prev].erase(x);
int cur=lca(a[x],a[x+1]);
s[cur].insert(x);
lcas[x]=cur;
}
}
}
return 0;
}
Compilation message
treearray.cpp: In function 'void prepare()':
treearray.cpp:32:11: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
32 | A[i][k]=-1;
| ~~~~~~~^~~
treearray.cpp:31:16: note: within this loop
31 | for(int k=1;k<=20;k++){
| ~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23796 KB |
Jury has the answer but participant has not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23796 KB |
Jury has the answer but participant has not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23796 KB |
Jury has the answer but participant has not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23796 KB |
Jury has the answer but participant has not |
| 2 |
Halted |
0 ms |
0 KB |
- |
