#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second
#define lpos pos*2
#define rpos pos*2+1
const int SIZE = 4005;
const int H = __lg (SIZE) + 2;
int n, m, q, cnt;
int h[SIZE], in[SIZE], out[SIZE], dfsp[SIZE];
int L[SIZE][H + 1], R[SIZE][H + 1], lc[4 * SIZE];
vector<int> adj[SIZE];
int a[SIZE];
int chmin (int i, int j) {
return h[i] < h[j] ? i : j;
}
int lca (int i, int j) {
int l = in[i], r = in[j];
if (l > r) swap (l, r);
int t = __lg (r - l + 1);
return chmin (L[l][t], R[r][t]);
}
void dfs (int pos, int fa) {
dfsp[++cnt] = pos;
in[pos] = out[pos] = cnt;
for (int np : adj[pos]) if (np != fa) {
h[np] = h[pos] + 1;
dfs (np, pos);
dfsp[++cnt] = pos;
out[pos] = cnt;
}
}
void Pull (int pos, int l, int r) {
lc[pos] = lca (lc[lpos], lc[rpos]);
}
void build (int pos, int l, int r) {
if (l == r) {
lc[pos] = a[l];
return;
}
int mid = (l + r) / 2;
build (lpos, l, mid);
build (rpos, mid + 1, r);
Pull (pos, l, r);
}
void upd (int pos, int l, int r, int p, int x) {
if (l == r) {
lc[pos] = x;
return;
}
int mid = (l + r) / 2;
if (p <= mid) upd (lpos, l, mid, p, x);
else upd (rpos, mid + 1, r, p, x);
Pull (pos, l, r);
}
int que (int pos, int l, int r, int L, int R) {
if (l > r) return 0;
if (l == L && r == R) return lc[pos];
int mid = (L + R) / 2;
if (r <= mid) return que (lpos, l, r, L, mid);
else if (l > mid) return que (rpos, l, r, mid + 1, R);
return lca (lc[lpos], lc[rpos]);
}
pair<int, int> cal (int l, int r, int v) {
for (int i = l, j = l - 1; i <= r; i++) {
j = max (j, i - 1);
while (j < r) {
j++;
int p = que (1, i, j, 1, m);
//cout << "i = " << i << ", j = " << j << ", p = " << p << '\n';
if (p == v) return {i, j};
if (h[p] <= h[v]) {j--; break;}
if (in[p] < in[v] || in[p] > out[v]) {j--; break;}
}
}
return {-1, -1};
}
void solve() {
cin >> n >> m >> q;
FOR (i, 2, n) {
int a, b;
cin >> a >> b;
adj[a].pb (b);
adj[b].pb (a);
}
h[1] = 1;
dfs (1, 1);
FOR (i, 1, cnt) L[i][0] = R[i][0] = dfsp[i];
for (int t = 1; (1 << t) < cnt; t++) {
int len = 1 << t, half = len >> 1;
FOR (i, 1, cnt - len + 1) L[i][t] = chmin (L[i][t - 1], L[i + half][t - 1]);
for (int i = cnt; i >= len; i--) R[i][t] = chmin (R[i][t - 1], R[i - half][t - 1]);
}
FOR (i, 1, m) cin >> a[i];
build (1, 1, m);
while (q--) {
int ty, l, r, p, v;
cin >> ty;
if (ty == 1) {
cin >> p >> v;
upd (1, 1, m, p, v);
a[p] = v;
} else {
cin >> l >> r >> v;
auto [x, y] = cal (l, r, v);
cout << x << ' ' << y << '\n';
}
}
}
int main() {
Waimai;
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n=5 |
| 2 |
Incorrect |
1 ms |
468 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n=5 |
| 2 |
Incorrect |
1 ms |
468 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n=5 |
| 2 |
Incorrect |
1 ms |
468 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
n=5 |
| 2 |
Incorrect |
1 ms |
468 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
