//bit chass 1
#include <bits/stdc++.h>
#define x first
#define y second
#define el "\n"
#define ll long long
#define pb push_back
#define pll pair <ll, ll>
#define pii pair <int, int>
#define all(x) x.begin(), x.end()
#define lcm(x,y) x * y / __gcd(x, y)
#define ibase ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
const int N = 2e5 + 5, inf = 1e9 + 7, M = 2e6, MM = 2e6 + 5, K = 300;
const ll MI = 2e18;
const double P = 3.14;
int a[N], tim, tin[N], tout[N], u[N][25], t[4 * N];
vector <int> g[N];
void dfs(int v, int pr) {
tin[v] = tim++;
u[v][0] = pr;
for (int i = 1; i <= 24; i++)
u[v][i] = u[u[v][i - 1]][i - 1];
for (int to : g[v]) {
if (to != pr)
dfs(to, v);
}
tout[v] = tim++;
}
bool up(int x, int y) {
if (tin[x] <= tin[y] && tin[y] <= tout[x])
return 1;
return 0;
}
int lca(int x, int y) {
if (up(x, y))
return x;
if (up(y, x))
return y;
for (int i = 24; i >= 0; i--) {
if (u[x][i] != 0 && !up(u[x][i], y))
x = u[x][i];
}
return u[x][0];
}
void build(int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
return;
}
int tm = (tl + tr) >> 1;
build(v + v, tl, tm);
build(v + v + 1, tm + 1, tr);
t[v] = lca(t[v + v], t[v + v + 1]);
}
void upd(int v, int tl, int tr, int pos, int val) {
if (tl == tr) {
t[v] = val;
return;
}
int tm = (tl + tr) >> 1;
if (pos <= tm)
upd(v + v, tl, tm, pos, val);
else
upd(v + v + 1, tm + 1, tr, pos, val);
t[v] = lca(t[v + v], t[v + v + 1]);
}
int get(int v, int tl, int tr, int l, int r) {
if (l <= tl && tr <= r)
return t[v];
if (r < tl || tr < l)
return -1;
int tm = (tl + tr) >> 1;
int pl = get(v + v, tl, tm, l, r), pr = get(v + v + 1, tm + 1, tr, l, r);
if (pl == pr && pr == -1)
return -1;
else if (pl == -1)
return pr;
else if (pr == -1)
return pl;
else
return (lca(pl, pr));
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 1, x, y; i < n; i++) {
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
tim = 1;
dfs(1, 0);
tout[0] = N;
for (int i = 1; i <= m; i++)
cin >> a[i];
build(1, 1, m);
while (q--) {
int tp;
cin >> tp;
if (tp == 1) {
int pos, v;
cin >> pos >> v;
upd(1, 1, m, pos, v);
}
else {
int l, r, v;
bool ok = 0;
cin >> l >> r >> v;
int tl = l - 1, tr = r, tm;
while (tr - tl > 1) {
tm = (tl + tr) >> 1;
int pl = tm, pr = tr + 1, pm;
while (pr - pl > 1) {
pm = (pl + pr) >> 1;
if (up(v, get(1, 1, m, tm, pm)))
pl = pm;
else
pr = pm;
}
if (get(1, 1, m, tm, pl) == v) {
cout << tm << ' ' << pl << el;
ok = 1;
break;
}
else if (up(v, get(1, 1, m, tm, pl)))
tr = tm;
else
tl = tm;
}
if (!ok)
cout << "-1 -1" << el;
}
}
}
int main() {
ibase;
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++) {
// cout << "Case " << i << ": ";
solve();
cout << el;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4940 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4940 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4940 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4940 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
