This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/// adil sultanov | vonat1us
#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:36777216")
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define sz(x) (int) x.size()
#define all(z) (z).begin(), (z).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 1e2;
void fin() {
#ifdef AM
freopen(".in", "r", stdin);
#endif
}
const bool flag = 0;
const int N = 2e5+10;
const int K = 18;
set<int> s[N], one[N];
vector<int> adj[N];
int up[K][N], tin[N], tout[N], tmr;
void dfs(int x = 0, int p = 0) {
up[0][x] = p;
for (int i = 1; i < K; ++i) {
up[i][x] = up[i-1][up[i-1][x]];
}
tin[x] = ++tmr;
for (int to : adj[x]) {
if (to != p) {
dfs(to, x);
}
}
tout[x] = tmr;
}
bool upper(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int i = K-1; ~i; --i) {
if (!upper(up[i][a], b)) {
a = up[i][a];
}
}
return up[0][a];
}
void ma1n() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].pb(v);
adj[v].pb(u);
}
vector<int> a(m);
for (int& x : a) cin >> x, x--;
dfs();
for (int i = 0; i < m; ++i) {
one[a[i]].insert(i);
if (i+1 < m) s[lca(a[i+1], a[i])].insert(i);
}
for (int i = 0; i < q; ++i) {
int t;
cin >> t;
if (t == 1) {
int pos, v;
cin >> pos >> v;
pos--, v--;
one[a[pos]].erase(pos);
if (pos+1 < m) s[lca(a[pos], a[pos+1])].erase(pos);
if (pos > 0) s[lca(a[pos], a[pos-1])].erase(pos-1);
a[pos] = v;
one[v].insert(pos);
if (pos+1 < m) s[lca(v, a[pos+1])].insert(pos);
if (pos > 0) s[lca(v, a[pos-1])].insert(pos-1);
} else {
int l, r, v;
cin >> l >> r >> v;
l--, r--, v--;
auto it = one[v].lower_bound(l);
if (it != one[v].end() && *it <= r) {
cout << *it+1 << " " << *it+1 << "\n";
continue;
}
it = s[v].lower_bound(l);
if (it != s[v].end() && *it < r) {
cout << *it+1 << " " << *it+2 << "\n";
} else {
cout << "-1 -1\n";
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr), fin();
int ts = 1;
if (flag) {
cin >> ts;
}
while (ts--) {
ma1n();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |