#include <bits/stdc++.h>
using namespace std;
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
using ll = long long;
constexpr int INF = (numeric_limits<int>::max()) / 2;
constexpr ll INFLL = (numeric_limits<ll>::max()) / 2;
template<class T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i: a) {
is >> i;
}
return is;
}
#ifdef __APPLE__
#include "debug.h"
#else
#define debug(...) 42
#endif
struct lca {
vector<vector<int>> g;
vector<int> depth;
vector<int> tin, tout;
vector<pair<int, int>> tour;
static constexpr int k = 20;
vector<vector<pair<int, int>>> st;
vector<int> prec;
void dfs(int v, int p) {
if (p != -1) {
depth[v] = depth[p] + 1;
}
tin[v] = tour.size();
tour.push_back({depth[v], v});
for (auto u: g[v]) {
if (u != p) {
dfs(u, v);
tour.push_back({depth[v], v});
}
}
tour.push_back({depth[v], v});
tout[v] = tour.size();
}
int getmin(int l, int r) {
int len = prec[r - l];
return min(st[len][l], st[len][r - (1 << len)]).second;
}
bool anc(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int LCA(int u, int v) {
if (anc(u, v)) {
return u;
}
if (anc(v, u)) {
return v;
}
if (tin[u] > tout[v]) {
swap(u, v);
}
return getmin(tin[u], tout[v]);
}
lca(vector<vector<int>> g) : g(g) {
int n = g.size();
depth.resize(n);
tin.resize(n);
tout.resize(n);
dfs(0, -1);
int m = tour.size();
prec.resize(m + 1);
for (int i = 2; i <= m; ++i) {
prec[i] = prec[i / 2] + 1;
}
st.resize(k, vector<pair<int, int>>(m, {INF, -1}));
for (int i = 0; i < m; ++i) {
st[0][i] = tour[i];
}
for (int i = 1; i < k; ++i) {
for (int j = 0; j < m; ++j) {
st[i][j] = min(st[i - 1][j], st[i - 1][min(m - 1, j + (1 << (i - 1)))]);
}
}
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
#endif
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
--u;
--v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> a(m);
cin >> a;
for (auto &i: a) {
--i;
}
vector<int> ap(m - 1);
lca t(g);
for (int i = 0; i + 1 < m; ++i) {
ap[i] = t.LCA(a[i], a[i + 1]);
}
debug(ap);
debug(t.tour);
vector<set<int>> inda(n);
for (int i = 0; i < m; ++i) {
inda[a[i]].insert(i);
}
vector<set<int>> indap(n);
for (int i = 0; i < m - 1; ++i) {
indap[ap[i]].insert(i);
}
auto calc = [&](int pos) {
if (pos >= 0 && pos + 1 < m) {
indap[ap[pos]].erase(pos);
ap[pos] = t.LCA(a[pos], a[pos + 1]);
indap[ap[pos]].insert(pos);
}
};
while (q--) {
int tt;
cin >> tt;
if (tt == 1) {
int pos, v;
cin >> pos >> v;
--pos;
--v;
inda[a[pos]].erase(pos);
a[pos] = v;
inda[a[pos]].insert(pos);
// for (int i = 0; i + 1 < m; ++i) {
// ap[i] = t.LCA(a[i], a[i + 1]);
// }
calc(pos);
calc(pos - 1);
} else {
int l, r, v;
cin >> l >> r >> v;
--l;// ap[l] is lca of (a[l], a[l + 1])
--r;// ap[r - 1] is lca of (a[r - 2], a[r - 1])
--v;
bool ans = false;
{
auto it = inda[v].lower_bound(l);
if (*it <= r) {
cout << *it + 1 << " " << *it + 1 << "\n";
ans = true;
}
}
if (!ans) {
auto it = indap[v].lower_bound(l);
if (*it < r) {
cout << *it + 1 << " " << *it + 2 << "\n";
ans = true;
}
}
// for (int i = l; i <= r; ++i) {
// if (a[i] == v) {
// cout << i + 1 << " " << i + 1 << "\n";
// ans = true;
// break;
// }
// }
// for (int i = l; i < r; ++i) {
// if (ap[i] == v && !ans) {
// cout << i + 1 << " " << i + 2 << "\n";
// ans = true;
// break;
// }
// }
if (!ans) {
cout << "-1 -1\n";
}
}
}
}
Compilation message
treearray.cpp: In function 'int main()':
treearray.cpp:21:20: warning: statement has no effect [-Wunused-value]
21 | #define debug(...) 42
| ^~
treearray.cpp:120:5: note: in expansion of macro 'debug'
120 | debug(ap);
| ^~~~~
treearray.cpp:21:20: warning: statement has no effect [-Wunused-value]
21 | #define debug(...) 42
| ^~
treearray.cpp:121:5: note: in expansion of macro 'debug'
121 | debug(t.tour);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Wrong range. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Wrong range. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Wrong range. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Wrong range. |
| 2 |
Halted |
0 ms |
0 KB |
- |
