//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define maxn 200005
int a[maxn], dep[maxn], anc[21][maxn];
vector<int> adj[maxn];
set<int> pos[maxn], pos2[maxn];
void dfs(int u, int p, int d){
dep[u] = d;
for(int v:adj[u]){
if(v == p) continue;
anc[0][v] = u;
dfs(v, u, d + 1);
}
}
int lca(int u, int v){
if(dep[v] > dep[u]) swap(u, v);
for(int i = 20; i >= 0; --i){
if(dep[anc[i][u]] >= dep[v]) u = anc[i][u];
}
if(u == v) return u;
for(int i = 20; i >= 0; --i){
if(anc[i][u] != anc[i][v]) u = anc[i][u], v = anc[i][v];
}
return anc[0][u];
}
void solve(){
int n, m, q; cin >> n >> m >> q;
for(int i = 1; i < n; ++i){
int u, v; cin >> u >> v;
adj[u].pb(v); adj[v].pb(u);
}
for(int i = 0; i <= 20; ++i) anc[i][1] = 1
dfs(1, 0, 0);
for(int i = 1; i <= 20; ++i){
for(int v = 2; v <= n; ++v){
anc[i][v] = anc[i - 1][anc[i - 1][v]];
}
}
for(int i = 1; i <= m; ++i) cin >> a[i], pos2[a[i]].insert(i);
for(int i = 1; i < m; ++i){
pos[lca(a[i], a[i + 1])].insert(i);
}
for(int i = 1; i <= q; ++i){
int t, l, r; cin >> t >> l >> r;
if(t == 1){
pos2[a[l]].erase(l);
pos2[r].insert(l);
if(l != n){
int u = lca(a[l], a[l + 1]);
pos[u].erase(l);
u = lca(r, a[l + 1]);
pos[u].insert(l);
}
if(i != 1){
int u = lca(a[l], a[l - 1]);
pos[u].erase(l - 1);
u = lca(r, a[l - 1]);
pos[u].insert(l - 1);
}
a[l] = r;
}else{
int v; cin >> v;
auto x = pos2[v].lower_bound(l);
if(x != pos2[v].end() && *x <= r) {
cout << *x << ' ' << *x << '\n';
continue;
}
x = pos[v].lower_bound(l);
if(x != pos[v].end() && *x < r){
cout << *x << ' ' << (*x) + 1 << '\n';
}else cout << "-1 -1\n";
}
}
}
signed main(){
starburst
int t = 1; //cin >> t;
while(t--) solve();
}
Compilation message
treearray.cpp: In function 'void solve()':
treearray.cpp:50:47: error: expected ';' before 'dfs'
50 | for(int i = 0; i <= 20; ++i) anc[i][1] = 1
| ^
| ;
51 | dfs(1, 0, 0);
| ~~~
