#include <bits/stdc++.h>
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define optimus_prime ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define fxd(x) fixed << setprecision(x)
#define all(a) (a.begin() , a.end())
#define popcount(x) __builtin_popcount(x)
#define lwb lower_bound
#define upb upper_bound
#define dl double long
#define ll long long
#define pb push_back
#define sz() size()
#define F first
#define S second
using namespace std;
const ll N = 1e5+9;
const ll L = 30;
ll n , m , q , a[N] , tin[N] , tout[N] , timer , h[N] , up[N][L];
vector <int> g[N];
set <int> st[N] , st1[N];
void calc(ll cur , ll p , ll len=1){
h[cur]=len;
tin[cur]=++timer;
up[cur][0]=p;
for (int i = 1 ; i <= L ; i++)up[cur][i]=up[up[cur][i-1]][i-1];
for (auto to : g[cur]){
if (to!=p)calc(to , cur , len+1);
}
tout[cur]=timer;
}
bool upper(ll a , ll b){
if (tin[a]<=tin[b]&&tout[b]<=tout[a])return 1;
return 0;
}
ll lca(ll a , ll b){
if (upper(a , b))return a;
if (upper(b , a))return b;
for (int i = L ; i >= 0 ; i--){
if (!upper(up[a][i] , b))a=up[a][i];
}
return up[a][0];
}
void solve(){
cin >> n >> m >> q;
for (int i = 1 ; i < n ; i++){
ll u , v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
calc(1 , 1);
for (int i = 1 ; i <= m ; i++){
cin >> a[i];
st[a[i]].insert(i);
if (i>1)st1[lca(a[i-1] , a[i])].insert(i-1);
}
while (q--){
ll tp;
cin >> tp;
if (tp==1){
ll pos , v;
cin >> pos >> v;
if (pos<m)st1[lca(a[pos] , a[pos+1])].erase(pos);
if (pos>1)st1[lca(a[pos-1] , a[pos])].erase(pos-1);
st[a[pos]].erase(pos);
a[pos]=v;
st[a[pos]].insert(pos);
if (pos<m)st1[lca(a[pos] , a[pos+1])].insert(pos);
if (pos>1)st1[lca(a[pos-1] , a[pos])].insert(pos-1);
}
else {
ll l , r , v;
cin >> l >> r >> v;
if (st[v].lwb(l)!=st[v].end() && (*st[v].lwb(l))<=r){
ll x=*(st[v].lwb(l));
cout << x << " " << x << "\n";
}
else if (st1[v].lwb(l)!=st1[v].end() && (*st1[v].lwb(l))<r){
ll x=*(st1[v].lwb(l));
cout << x << " " << x+1 << "\n";
}
else cout << "-1 -1\n";
}
}
}
signed main() {
optimus_prime;
solve();
return 0;
}
Compilation message
treearray.cpp: In function 'void calc(long long int, long long int, long long int)':
treearray.cpp:30:42: warning: iteration 29 invokes undefined behavior [-Waggressive-loop-optimizations]
30 | for (int i = 1 ; i <= L ; i++)up[cur][i]=up[up[cur][i-1]][i-1];
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:30:21: note: within this loop
30 | for (int i = 1 ; i <= L ; i++)up[cur][i]=up[up[cur][i-1]][i-1];
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14940 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
14936 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14940 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
14936 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14940 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
14936 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14940 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
14936 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
