#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<": "<<x<<endl;
using namespace std;
const int maxn=2e5+19;
vector<int>T[maxn];
int tin[maxn];
int tout[maxn];
int timer=0;
vector<pair<int,int>>euler_path;
int min_tin[maxn];
int h[maxn];
void gfs(int v, int p){
tin[v]=++timer;
min_tin[v]=euler_path.size();
euler_path.push_back({h[v],v});
for(auto u:T[v]){
if(u==p)continue;
h[u]=h[v]+1;
gfs(u,v);
euler_path.push_back({h[v],v});
}
tout[v]=++timer;
}
const int Q=1<<18;
pair<int,int>tree[2*Q];
int lca_tree[2*Q];
const int inf=1e9;
void update(int p, pair<int,int>x) {
p+=Q;
tree[p]=x;
p/=2;
while(p>0){
tree[p]=min(tree[p*2],tree[2*p+1]);
p/=2;
}
}
pair<int,int> get(int l, int r) {
pair<int,int> ans={inf,inf};
for(l+=Q,r+=Q;l<r;l>>=1,r>>=1){
if(l&1)ans=min(ans,tree[l++]);
if(r&1)ans=min(ans,tree[--r]);
}
return ans;
}
int lca(int x, int y);
void update_lca_tree(int p, int x) {
p+=Q;
lca_tree[p]=x;
p/=2;
while(p>0){
lca_tree[p]=lca(lca_tree[2*p],lca_tree[2*p+1]);
p/=2;
}
}
int get_lca(int l, int r) {
int ans=-1;
for(l+=Q,r+=Q;l<r;l/=2,r/=2){
if(l&1) ans=lca(ans,lca_tree[l++]);
if(r&1) ans=lca(ans,lca_tree[--r]);
}
return ans;
}
int lca(int x, int y) {
if(x==-1)return y;
if(min_tin[x]>min_tin[y]){
swap(x,y);
}
pair<int,int> ans=get(min_tin[x],min_tin[y]+1);
return ans.second;
}
bool check_subtree(int root, int child) {
return tin[root] <= tin[child] && tout[child]<=tout[root];
}
int main() {
fill(tree,tree+2*Q,make_pair(inf,inf));
memset(lca_tree,255,sizeof(lca_tree));
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
int m;
cin>>m;
int q;
cin>>q;
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
T[a].push_back(b);
T[b].push_back(a);
}
gfs(1,-1);
for(int i=0;i<(int)euler_path.size();i++){
update(i,euler_path[i]);
}
vector<int>a(m);
for(int i=0;i<m;i++){
cin>>a[i];
update_lca_tree(i,a[i]);
}
for(;q;q--){
int t;
cin>>t;
if(t==1) {
int pos,v;
cin>>pos>>v;
pos--;
a[pos]=v;
update_lca_tree(pos,v);
}
if(t==2) {
int l,r,v;
cin>>l>>r>>v;
l--;r--;
int check=get_lca(l,r+1);
if(!check_subtree(check,v)) {
cout<<"-1 -1\n";
continue;
}
int L=l;
int R=r+1;
while(R-L>1){
int M=(L+R)/2;
int max_lca=get_lca(M,r+1);
if(check_subtree(max_lca,v)){
L=M;
} else {
R=M;
}
}
int left=L;
// debug(left);
L=left-1,R=r;
while(R-L>1){
int M=(L+R)/2;
int max_lca=get_lca(left,M+1);
if(check_subtree(max_lca,v)){
R=M;
} else {
L=M;
}
}
int right=R;
check=get_lca(left,right+1);
if(check==v) {
cout<<left+1<<" "<<right+1<<"\n";
} else {
int L=l-1;
int R=r;
while(R-L>1){
int M=(L+R)/2;
int max_lca=get_lca(l,M+1);
if(check_subtree(max_lca,v)){
R=M;
} else {
L=M;
}
}
int right=R;
L=l,R=right+1;
while(R-L>1){
int M=(L+R)/2;
int max_lca=get_lca(M,right+1);
if(check_subtree(max_lca,v)){
L=M;
} else {
R=M;
}
}
int left=L;
check=get_lca(left,right+1);
if(check==v){
cout<<left+1<<" "<<right+1<<"\n";
}
else {
cout<<"-1 -1\n";
}
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11256 KB |
n=5 |
| 2 |
Incorrect |
12 ms |
11256 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11256 KB |
n=5 |
| 2 |
Incorrect |
12 ms |
11256 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11256 KB |
n=5 |
| 2 |
Incorrect |
12 ms |
11256 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11256 KB |
n=5 |
| 2 |
Incorrect |
12 ms |
11256 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
