#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less_equal <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10;
vector <int> g[N];
int up[N][22], tin[N], tout[N], timer = 0;
inline void dfs (int v, int p) {
up[v][0] = p; tin[v] = timer++;
for (int i = 1; i < 20; ++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++;
}
inline bool upper (int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; }
inline int lca (int a, int b) {
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int i = 19; ~i; --i) if (!upper(up[a][i], b)) a = up[a][i];
return up[a][0];
}
inline void solve () {
int n, m, q; cin >> n >> m >> q;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v; --u; --v;
g[u].pb(v); g[v].pb(u);
}
dfs(0, 0);
vector <int> a (m);
for (auto &i : a) cin >> i, --i;
vector <set <int>> ps (n), pss (n);
for (int i = 0; i < m; ++i) {
ps[a[i]].insert(i);
if (i) pss[lca(a[i - 1], a[i])].insert(i);
}
while (q--) {
int tp; cin >> tp;
if (tp == 1) {
int pos, v; cin >> pos >> v; --pos, --v;
ps[a[pos]].erase(pos);
if (pos) pss[lca(a[pos - 1], a[pos])].erase(pos);
if (pos + 1 < m) ps[lca(a[pos], a[pos + 1])].erase(pos + 1);
a[pos] = v;
ps[a[pos]].insert(pos);
if (pos) pss[lca(a[pos - 1], a[pos])].insert(pos);
if (pos + 1 < m) ps[lca(a[pos], a[pos + 1])].insert(pos + 1);
}
else {
int l, r, v; cin >> l >> r >> v; --l, --r, --v;
auto it = ps[v].lower_bound(l);
if (it != ps[v].end() && *it <= r) cout << *it + 1 << " " << *it + 1 << endl;
else {
auto itt = pss[v].lower_bound(l + 1);
if (itt != pss[v].end() && *itt <= r) cout << *itt << " " << *itt + 1 << endl;
else cout << -1 << " " << -1 << endl;
}
}
}
}
/// [a [b c]]
/// [[a b] c]
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1; // cin >> t;
while (t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4948 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4948 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4948 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4948 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
