#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
const int LOG=18;
set<pair<int,pair<int,int> > > it[N<<2];
vector<int> adj[N];
int level[N],ancestor[LOG][N],ar[N],lst,lef,rig;
void dfs(int x,int p){
for(int i=1;i<LOG;i++){
ancestor[i][x]=ancestor[i-1][ancestor[i-1][x]];
}
for(auto i:adj[x]){
if(i!=p){
level[i]=level[x]+1;
ancestor[0][i]=x;
dfs(i,x);
}
}
}
void print(int idx,int l,int r){
cout<<idx<<' '<<l<<' '<<r<<" START\n";
for(auto ite=it[idx].begin();ite!=it[idx].end();ite++){
cout<<ite->first<<' '<<ite->second.first<<' '<<ite->second.second<<endl;
}
cout<<"END"<<endl;
}
int findd(int x,int k){
while(k){
int y=__lg(k);
x=ancestor[y][x];
k-=(1<<y);
}
return x;
}
int LCA(int x,int y){
if(level[x]>level[y]){
x=findd(x,level[x]-level[y]);
}
y=findd(y,level[y]-level[x]);
if(x==y){
return x;
}
for(int i=LOG-1;i>-1;i--){
if(ancestor[i][x]!=ancestor[i][y]){
x=ancestor[i][x],y=ancestor[i][y];
}
}
return ancestor[0][x];
}
void upd(int idx,int l,int r,int l1,int r1,int val){
if(l>r1||r<l1){
return;
}
if(l<=l1&&r>=r1){
it[idx].insert({val,{l1,r1}});
}
if(l>=l1&&r<=r1){
return;
}
upd(2*idx,l,(l+r)/2,l1,r1,val);
upd(2*idx+1,(l+r)/2+1,r,l1,r1,val);
}
void upd1(int idx,int l,int r,int l1,int r1,int val){
if(l>r1||r<l1){
return;
}
if(l<=l1&&r>=r1){
it[idx].erase({val,{l1,r1}});
}
if(l>=l1&&r<=r1){
return;
}
upd1(2*idx,l,(l+r)/2,l1,r1,val);
upd1(2*idx+1,(l+r)/2+1,r,l1,r1,val);
}
void query(int idx,int l,int r,int l1,int r1,int val){
if(lef!=-1){
return;
}
if(l>r1||r<l1){
return;
}
if(l>=l1&&r<=r1){
// print(idx,l,r);
auto ite=it[idx].lower_bound({val,{0,0}});
if(ite!=it[idx].end()&&ite->first==val){
lef=ite->second.first;
rig=ite->second.second;
}
if(r<r1){
if(val==LCA(ar[r],ar[r+1])){
lef=r;
rig=r+1;
}
}
return;
}
query(2*idx,l,(l+r)/2,l1,r1,val);
query(2*idx+1,(l+r)/2+1,r,l1,r1,val);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,i,j,k,l,m,q;
cin>>n>>m>>q;
for(i=1;i<n;i++){
cin>>j>>k;
adj[j].push_back(k);
adj[k].push_back(j);
}
dfs(1,1);
for(i=1;i<=m;i++){
cin>>ar[i];
upd(1,1,m,i,i,ar[i]);
if(i>1){
upd(1,1,m,i-1,i,LCA(ar[i-1],ar[i]));
}
}
cout<<LCA(4,5)<<endl;
for(i=1;i<=q;i++){
cin>>j;
if(j==1){
cin>>k>>l;
upd1(1,1,m,k,k,ar[k]);
if(k>1){
upd1(1,1,m,k-1,k,LCA(ar[k-1],ar[k]));
}
if(k<m){
upd1(1,1,m,k,k+1,LCA(ar[k],ar[k+1]));
}
ar[k]=l;
upd(1,1,m,k,k,ar[k]);
if(k>1){
upd(1,1,m,k-1,k,LCA(ar[k-1],ar[k]));
}
if(k<m){
upd(1,1,m,k,k+1,LCA(ar[k],ar[k+1]));
}
}
else{
cin>>j>>k>>l;
lef=rig=-1;
query(1,1,m,j,k,l);
cout<<lef<<' '<<rig<<'\n';
}
}
}
/*
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
42744 KB |
Wrong output format. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
42744 KB |
Wrong output format. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
42744 KB |
Wrong output format. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
42744 KB |
Wrong output format. |
| 2 |
Halted |
0 ms |
0 KB |
- |
