#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
const int K = 19;
int up[N][K], a[N], tin[N], tout[N], timer, m;
int n, q, st[4 * N];
vector<int> g[N];
bool anc(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int Lca(int a, int b) {
if (anc(a, b))
return a;
else if (anc(b, a))
return b;
for (int i = K - 1;i >= 0;i--) {
if (!anc(up[a][i], b) && up[a][i] > 0)
a = up[a][i];
}
return up[a][0];
}
void dfs(int v, int p) {
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1;i < K;i++)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto u : g[v]) {
if (u == p)
continue;
dfs(u, v);
}
tout[v] = timer;
}
void modify(int v, int tl, int tr, int p, int x) {
if (tl == tr)
st[v] = x;
else {
int mid = (tl + tr) / 2;
if (p <= mid)
modify(v * 2, tl, mid, p, x);
else
modify(v * 2 + 1, mid + 1, tr, p, x);
st[v] = Lca(st[v * 2], st[v * 2 + 1]);
}
}
int get(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return -1;
else if (tl >= l && tr <= r)
return st[v];
else {
int mid = (tl + tr) / 2;
int left = get(v * 2, tl, mid, l, r);
int right = get(v * 2 + 1, mid + 1, tr, l, r);
assert(left != -1 || right != -1);
if (left != -1 && right != -1)
return Lca(left, right);
else if (left != -1)
return left;
else
return right;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> m >> q;
for (int i = 1;i <= n - 1;i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1;i <= m;i++) {
cin >> a[i];
modify(1, 1, m, i, a[i]);
}
dfs(1, 0);
while (q--) {
int t;
cin >> t;
if (t == 1) {
int pos, v;
cin >> pos >> v;
modify(1, 1, m, pos, v);
a[pos] = v;
}
else {
int tl, tr, v;
cin >> tl >> tr >> v;
int x = -1, y = -1;
for (int i = tl;i <= tr;i++) {
int l = tl, r = i, id = i;
if (!anc(v, a[i]))
continue;
while (l <= r) {
int mid = (l + r) / 2;
int x = get(1, 1, m, mid, i);
if (anc(x, v)) {
l = mid + 1;
id = mid;
}
else
r = mid - 1;
}
int t = get(1, 1, m, id, i);
if (t == v) {
x = id, y = i;
break;
}
}
cout << x << ' ' << y << '\n';
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12888 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
12892 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 |
12888 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
12892 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 |
12888 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
12892 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 |
12888 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
12892 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
