| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 672957 | 2022-12-19T07:56:54 Z | ReLice | Birthday gift (IZhO18_treearray) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define ld long double
#define int long long
#define pb push_back
#define sz size()
#define fr first
#define sc second
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
void fre(string n){freopen((n+".in").c_str(),"r",stdin);freopen((n+".out").c_str(),"w",stdin);}
const ll N = 2e5 + 5 ;
const ll inf=1e9+7;
ll l,a,c=0;
ll d[N];
vector <vector <ll>> up(N),g(N);
void dfs(ll v,ll pr){
up[v][0]=pr;
if(v!=a) {
bool flag=false;
for(ll i=1;i<=c;i++){
if(flag){
up[v][i]=0;
continue;
}
up[v][i]=up[up[v][i-1]][i-1];
if(up[v][i]==0) flag =true;
}
}
else {
for(ll i=0;i<=c;i++){
up[v][i]=0;
}
}
for(auto i : g[v]){
if(i==up[v][0]) continue;
d[i]=d[v]+1;
dfs(i,v);
}
}
ll lca(ll v,ll u){
if(d[u]<d[v]) swap(u,v);
ll i=c;
while(d[u]>d[v] && i>=0){
if(d[up[u][i]]<d[v])i--;
else {
u=up[u][i];
i--;
}
}
i=c;
if(u==v) return u;
while(i>=0){
if(up[u][i]==up[v][i]) {i--;}
else {
u=up[u][i];
v=up[v][i];
i--;
}
}
return up[u][0];
}
void solve(){
ll n,m,b,b1,k,i,q,j,mx=-1;
cin>>n>>m>>q;
l=1;
vector <map<ll,ll>> mp(n+5);
vector <ll> v;
vector <set<ll>> ans(n+5);
while(l<n) {c++;l*=2;}
for(i=1;i<=n;i++){
up[i].resize(c+2);
}
for(i=1;i<n;i++){
cin>>k>>b;
g[b].pb(k);
g[k].pb(b);
}
d[0]=-1;
d[1]=0;
a=1;
dfs(1,0);
v.pb(0);
for(i=0;i<m;i++){
cin>>b;
v.pb(b);
}
for(i=2;i<=m;i++){
b=lca(v[i],v[i-1]);
ans[b].insert(i-1);
mp[b][i-1]=2;
}
for(i=1;i<=m;i++){
ans[v[i]].insert(i);
mp[v[i]][i]=1;
}
while(q--){
ll tp;
cin>>tp;
if(tp==1){
cin>>b>>b1;
if(b>0){
ans[lca(v[b],v[b-1])].erase(b-1);
mp[lca(v[b],v[b-1])][b-1]=0;
}
if(b<m-1){
ans[lca(v[b],v[b+1])].erase(b);
mp[lca(v[b],v[b+1])][b]=0;
}
ans[v[b]].erase(b);
mp[v[b]][b]=0;
v[b]=b1;
if(b>0){
ans[lca(v[b],v[b-1])].insert(b-1);
mp[lca(v[b],v[b-1])][b-1]=2;
}
if(b<m-1){
ans[lca(v[b],v[b+1])].insert(b);
mp[lca(v[b],v[b+1])][b]=2;
}
ans[v[b]].insert(b);
mp[v[b]][b]=1;
}
else {
cin>>b>>b1>>k;
auto it = ans[k].lower_bound(b);
if(*it <= b1){
if(mp[k][*it]>=2 && it*<b1) cout<<*it<<' '<<*it+1<<endl;
else if(mp[k][*it]!=2) cout<<*it<<' '<<*it<<endl;
}
else cout<<-1<<' '<<-1<<endl;
}
}
}
main(){
//fre("");
start();
ll t=1;
//cin>>t;
while(t--)solve();
}
/*
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
*/