// 以上帝的名义
// 候选硕士
#include <bits/stdc++.h>
#ifdef local
#include "algo/debug.h"
#else
#define dbg(x...) 0
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define Node int
#define at(i) find_by_order(i)
#define which(x) order_of_key(x)
#define SET tree<Node, null_type,less<Node>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 2e5 + 5 ;
int n , m , q, a[N], p[N] ;
vector<int> g[N] ;
int tin[N], tout[N], timer , up[N][20] ;
void dfs(int v, int p) {
tin[v] = ++timer ;
up[v][0] = p ;
for (int i = 1 ; i < 20 ; i++) {
up[v][i] = up[up[v][i - 1]][i - 1] ;
}
for (auto to : g[v]) {
if (to != p) {
dfs(to, v) ;
}
}
tout[v] = ++timer ;
}
bool is(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v] ;
}
bool upper(int u, int v) {
return tin[u] < tin[v] && tout[u] > tout[v] ;
}
int lca(int u, int v) {
if (!u) return v ;
if (!v) return u ;
if (is(u, v)) return u ;
if (is(v, u)) return v ;
for (int i = 19 ; ~i ; i--) {
if (!is(up[u][i], v)) {
u = up[u][i] ;
}
}
return up[u][0] ;
}
int t[N * 4] ;
void modify(int i, int x, int v, int tl, int tr) {
if (tl == tr) {
t[v] = x ;
} else {
int tm = (tl + tr) / 2 ;
if (i <= tm) {
modify(i, x, v * 2, tl, tm) ;
} else {
modify(i, x, v * 2 + 1, tm + 1, tr) ;
}
t[v] = lca(t[v * 2], t[v * 2 + 1]) ;
}
}
int get(int l, int r, int v, int tl, int tr) {
if (l > tr || r < tl) return 0 ;
if (l <= tl && tr <= r) return t[v] ;
int tm = (tl + tr) / 2 ;
return lca(get(l, r,v * 2, tl, tm), get(l, r,v * 2 + 1 ,tm + 1, tr)) ;
}
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
int find(int i, int L, int R, int v) {
int l = i, r = R ;
while (l < r) {
int mid = (l + r + 1) / 2 ;
int c = get(i, mid, 1, 1 , m) ;
if (upper(c, v)) r = mid - 1 ;
else l = mid ;
}
return l ;
}
int32_t main() {
ios::sync_with_stdio(false) ;
cin.tie(nullptr) ;
cin >> n >> m >> q ;
for (int i = 1 ; i < n ; i++) {
int u , v ; cin >> u >> v;
g[u].push_back(v) ;
g[v].push_back(u) ;
}
for (int i = 1 ; i <= m ; i++) {
cin >> a[i] ;
p[a[i]] = i ;
}
dfs(1, 1) ;
for (int i = 1 ; i <= m ; i++) {
modify(i, a[i], 1, 1, m) ;
}
// dbg(get(1, 2, 1, 1, m)) ;
for (int i = 0 ; i < q ; i++) {
int cmd ; cin >> cmd ;
if (cmd == 1) {
int pos, v; cin >> pos >> v ;
modify(pos, v, 1, 1, m) ;
} else {
int L, R, v;
cin >> L >> R >> v ;
int l = L, r = R ;
int _l = -1 , _r = -1 ;
while (l <= r) {
int m1 = l + (r - l) / 3 ;
int m2 = r - (r - l) / 3 ;
int r1 = find(m1, L, R, v) ;
int r2 = find(m2 , L, R, v) ;
if (get(m1, r1, 1, 1, m) == v) _l = m1, _r = r1 ;
if (get(m2, r2, 1, 1, m) == v) _l = m2, _r = r2 ;
if (upper(m1, m2)) l = m1 + 1 ;
else r = m2 - 1 ;
}
cout << _l << ' ' << _r << "\n" ;
}
}
return 0 ;
}
// 希望白银
Compilation message
treearray.cpp:90: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
90 | #pragma GCC optimization ("O3")
|
treearray.cpp:91: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
91 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
8796 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 |
8796 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
8796 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 |
8796 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
8796 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 |
8796 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
8796 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
