#include<bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define R(i, a, b) for(int i = (a); i >= (b); --i)
#define N(a)(int)a.size()
#define full(a)a.begin(),a.end()
using namespace std;
template<typename t>inline void sort(vector<t>&a){sort(full(a));}
template<typename t>inline void uni(vector<t>&a){sort(a);a.erase(unique(full(a)),a.end());}
const int data_size=1<<20;
char Data[data_size];
char rchar(){
static int pos=0,len=0;
if(pos==len){
pos=0;
len=(int)fread(Data,1,data_size,stdin);
if(!len)return EOF;
}
return Data[pos++];
}
template<typename t>void read(t &x){
x=0;
bool neg=false;
char c=rchar();
if(c=='-')neg=true,c=rchar();
for(;c>='0'&&c<='9';c=rchar())(x*=10)+=c-'0';
if(neg)x=-x;
}
template<typename m, typename ...t>void read(m& _m, t&... _t){
read(_m);
read(_t...);
}
//...
const int MN=2e5+1;
int n,m,q,a[MN],h[MN],par[18][MN];
vector<int>g[MN];
set<int>single[MN],couple[MN];
void dfs(int v){
for(int &x:g[v])if(x!=par[0][v]){
h[x]=h[v]+1;
par[0][x]=v;
F(i,1,17)par[i][x]=par[i-1][par[i-1][x]];
dfs(x);
}
}
int lca(int u,int v){
if(h[u]<h[v])u^=v^=u^=v;
F(i,0,17)if((h[u]-h[v])&(1<<i))u=par[i][u];
if(u==v)return u;
R(i,17,0)if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v];
return par[0][u];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
read(n,m,q);
F(i,1,n-1){
int u,v;read(u,v);
g[u].push_back(v);
g[v].push_back(u);
}
par[0][1]=1;
dfs(1);
F(i,1,m){
read(a[i]);
single[a[i]].insert(i);
if(i>1)couple[lca(a[i-1],a[i])].insert(i-1);
}
while(q--){
int t;read(t);
if(t==1){
int p,v;read(p,v);
if(a[p]==v)continue;
single[a[p]].erase(p);
single[v].insert(p);
if(p>1){
couple[lca(a[p-1],a[p])].erase(p-1);
couple[lca(a[p-1],v)].insert(p-1);
}
if(p<m){
couple[lca(a[p],a[p+1])].erase(p);
couple[lca(v,a[p+1])].insert(p);
}
a[p]=v;
}
else{
int l,r,v;read(l,r,v);
set<int>::iterator it=single[v].lower_bound(l);
if(it!=single[v].end()&&*it<=r){cout<<*it<<' '<<*it<<'\n';continue;}
it=couple[v].lower_bound(l-1);
if(it!=couple[v].end()&&*it<r){cout<<*it<<' '<<*it+1<<'\n';continue;}
cout<<"-1 -1\n";
}
}
cerr<<"runtime: "<<(1.0*clock()/CLOCKS_PER_SEC)<<"s\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |