#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
ll INF=1e18+10;
int inf=2e9+10;
ll M=1e9+7;
int n,ms,q,k;
vii a,p;
vi br,as,ae;
vector<map<int,multiset<int>>> st;
int f=0,g=0;
void dfs(int x){
as[x]=f++;
for(auto u:a[x]){
if(as[u]!=-1)continue;
p[u][0]=x;
dfs(u);
}
ae[x]=g++;
}
bool ances(int x,int y){
if(y==-1)return 1;
if(as[x]>=as[y]&&ae[x]<=ae[y])return 1;
return 0;
}
int LCA(int x,int y){
if(ances(x,y))return y;
if(ances(y,x))return x;
for(int i=k-1;i>=0;i--)if(!ances(x,p[y][i]))y=p[y][i];
return p[y][0];
}
void build(int x,int l,int r){
if(l==r){
st[x][br[l]].insert(l);
return;
}
int m=(l+r)/2;
build(2*x,l,m);
build(2*x+1,m+1,r);
for(auto u:st[2*x])st[x][u.F]=u.S;
for(auto u:st[2*x+1])for(auto v:u.S)st[x][u.F].insert(v);
int y=LCA(br[m],br[m+1]);
st[x][y].insert(m);
}
void update(int x,int l,int r,int p,int v){
if(l==r){
st[x][br[p]].erase(p);
st[x][v].insert(p);
if(l==r)return;
}
int m=(l+r)/2;
if(m>=p)update(2*x,l,m,p,v);
else update(2*x+1,m+1,r,p,v);
st[x].clear();
for(auto u:st[2*x])st[x][u.F]=u.S;
for(auto u:st[2*x+1])for(auto v:u.S)st[x][u.F].insert(v);
int y=LCA(v,br[m+1]);
st[x][y].insert(m);
}
int solve(int x,int l,int r,int a,int b,int v){
if(a>b)return -1;
if(l==a&&r==b){
if(st[x][v].empty())return -1;
auto it=st[x][v].begin();
return *it;
}
int m=(l+r)/2;
if(a<=m&&m<=b&&LCA(br[m],br[m+1])==v)return m;
return max(solve(2*x,l,m,a,min(b,m),v),solve(2*x+1,m+1,r,max(a,m+1),b,v));
}
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
cin>>n>>ms>>q;
k=ceil(log2(n))+1;
a.resize(n);p.resize(n,vi(k,-1));as.resize(n,-1);ae.resize(n,-1);br.resize(ms);
REP(i,0,n-1){
int x,y;cin>>x>>y;
x--;y--;
a[x].PB(y);
a[y].PB(x);
}
REP(i,0,ms)cin>>br[i];
REP(i,0,ms)br[i]--;
dfs(0);
REP(j,1,k)REP(i,0,n)if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];
st.resize(4*ms+1);
build(1,0,ms-1);
while(q--){
int t;cin>>t;
if(t==1){
int x,y;cin>>x>>y;
x--;y--;
update(1,0,ms-1,x,y);
br[x]=y;
}
else{
int l,r,x;cin>>l>>r>>x;
l--;r--;x--;
int ans=solve(1,0,ms-1,l,r,x);
if(ans==-1)cout<<-1<<" "<<-1<<endl;
else if(br[ans]==x)cout<<ans+1<<" "<<ans+1<<endl;
else cout<<ans+1<<" "<<ans+2<<endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
604 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
604 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
604 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
604 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
