#include<bits/stdc++.h>
using namespace std;
int n,m,q;
const int maxn=200000+10;
vector<int>adj[maxn];
int timea=0;
pair<int,int>stf[maxn];
int lca[19][maxn];
void dfs(int u,int par=0){
timea++;
stf[u].first=timea;
lca[0][u]=par;
for(auto x:adj[u]){
if(x==par){
continue;
}
dfs(x,u);
}
stf[u].second=timea;
}
void callca(){
for(int i=1;i<19;i++){
for(int j=1;j<=n;j++){
lca[i][j]=lca[i-1][lca[i-1][j]];
}
}
}
bool zird(int u,int v){
if(stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second){
return 1;
}
return 0;
}
int getlca(int u,int v){
if(zird(u,v)){
return v;
}
if(zird(v,u)){
return u;
}
for(int i=18;i>=0;i--){
if(lca[i][u]!=0&&!zird(v,lca[i][u])){
u=lca[i][u];
}
}
u=lca[0][u];
return u;
}
int kaf=(1<<18);
struct segment{
map<int,int>seg[(1<<19)];
void upd(int i,int v,int wher){
if(i==0){
return ;
}
if((i<<1)>=(1<<19)){
seg[i][v]=wher;
return upd((i>>1),v,wher);
}
if(seg[(i<<1)].count(v)==0){
seg[i][v]=seg[(i<<1)^1][v];
}
else if(seg[(i<<1)^1].count(v)==0){
seg[i][v]=seg[(i<<1)][v];
}
else{
seg[i][v]=min(seg[(i<<1)][v],seg[(i<<1)^1][v]);
}
return upd((i>>1),v,wher);
}
int pors(int i,int l,int r,int tl,int tr,int v){
if(l>r||l>tr||r<tl||seg[i].count(v)==0){
return m+2;
}
if(l>=tl&&r<=tr){
return seg[i][v];
}
int ma=(l+r)>>1;
int ret=pors((i<<1),l,ma,tl,tr,v);
if(ret==m+2){
ret=pors((i<<1)^1,ma+1,r,tl,tr,v);
}
return ret;
}
}seg;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>q;
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
callca();
vector<int>allm(m);
for(int i=0;i<m;i++){
cin>>allm[i];
}
for(int i=0;i<m;i++){
seg.upd(kaf+i,allm[i],i);
if(i!=m-1){
seg.upd(kaf+i,getlca(allm[i],allm[i+1]),i);
}
}
for(int i=0;i<q;i++){
int qq;
cin>>qq;
if(qq==1){
int ind,v;
cin>>ind>>v;
ind--;
seg.upd(kaf+ind,allm[ind],m+2);
if(ind!=m-1){
seg.upd(kaf+ind,getlca(allm[ind],allm[ind+1]),m+2);
}
if(ind!=0){
seg.upd(kaf+ind-1,getlca(allm[ind],allm[ind-1]),m+2);
}
allm[ind]=v;
seg.upd(kaf+ind,allm[ind],ind);
if(ind!=m-1){
seg.upd(kaf+ind,getlca(allm[ind],allm[ind+1]),ind);
}
if(ind!=0){
seg.upd(kaf+ind-1,getlca(allm[ind],allm[ind-1]),ind-1);
}
}
else{
int l,r,v;
cin>>l>>r>>v;
l--;
r--;
int w=seg.pors(1,0,kaf-1,l,r,v);
if(w==m+2){
cout<<-1<<" "<<-1<<"\n";
continue;
}
if(allm[w]==v){
cout<<w+1<<" "<<w+1<<"\n";
}
else{
cout<<w+1<<" "<<w+1+1<<"\n";
}
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
29652 KB |
n=5 |
| 2 |
Correct |
16 ms |
29780 KB |
n=100 |
| 3 |
Correct |
20 ms |
29752 KB |
n=100 |
| 4 |
Correct |
18 ms |
29860 KB |
n=100 |
| 5 |
Incorrect |
17 ms |
29780 KB |
Jury has the answer but participant has not |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
29652 KB |
n=5 |
| 2 |
Correct |
16 ms |
29780 KB |
n=100 |
| 3 |
Correct |
20 ms |
29752 KB |
n=100 |
| 4 |
Correct |
18 ms |
29860 KB |
n=100 |
| 5 |
Incorrect |
17 ms |
29780 KB |
Jury has the answer but participant has not |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
29652 KB |
n=5 |
| 2 |
Correct |
16 ms |
29780 KB |
n=100 |
| 3 |
Correct |
20 ms |
29752 KB |
n=100 |
| 4 |
Correct |
18 ms |
29860 KB |
n=100 |
| 5 |
Incorrect |
17 ms |
29780 KB |
Jury has the answer but participant has not |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
29652 KB |
n=5 |
| 2 |
Correct |
16 ms |
29780 KB |
n=100 |
| 3 |
Correct |
20 ms |
29752 KB |
n=100 |
| 4 |
Correct |
18 ms |
29860 KB |
n=100 |
| 5 |
Incorrect |
17 ms |
29780 KB |
Jury has the answer but participant has not |
| 6 |
Halted |
0 ms |
0 KB |
- |
