#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e6 + 5;
const int LOG = 21;
int uzyn[N], dp[N][LOG], height[N], a[N];
vector <int> v[N];
void dfs (int x, int par, int height) {
uzyn[x] = height;
dp[x][0] = par;
for (int i : v[x]) {
if (i == par) continue;
dfs (i, x, height + 1);
}
}
int kth_ancestor (int x, int k) {
for (int i = LOG - 1; i >= 0; i--) {
if (k>>i&1) {
x = dp[x][i];
}
}
return x;
}
int lca (int x, int y) {
if (height[x] < uzyn[y]) {
y = kth_ancestor (y, uzyn[y] - uzyn[x]);
}
if (height[x] > height[y]) {
x = kth_ancestor (x, uzyn[x] - uzyn[y]);
}
for (int i = LOG - 1; i >= 0; i--) {
if (dp[x][i] != dp[y][i]) {
x = dp[x][i];
y = dp[y][i];
}
}
return dp[x][0];
}
int main () {
// freopen ("input.txt", "r", stdin);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i < n; ++i) {
int l, r;
cin >> l >> r;
v[l].pb (r);
v[r].pb (l);
}
set <int> s[n + 1], s1[n + 1];
dfs (1, -1, 0);
for (int i = 1; i < LOG; ++i) {
for (int j = 1; j <= n; ++j) {
dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
}
for (int i = 1; i <= m; ++i) {
cin >> a[i];
s[a[i]].insert (i);
if (i > 1) {
s1[lca (a[i], a[i - 1])].insert (i - 1);
// cout << a[i] << " " << a[i - 1] << "--> " << lca (a[i], a[i - 1]) << "\n";
}
}
while ( q-- ) {
int tp;
cin >> tp;
if (tp == 1) {
int pos, val;
cin >> pos >> val;
// update
s[a[pos]].erase (pos);
s[val].insert (pos);
if (pos > 1) {
s1[lca (a[pos], a[pos - 1])].erase (pos - 1);
s1[lca (a[pos - 1], val)].insert (pos - 1);
}
if (pos < n) {
s1[lca (a[pos], a[pos + 1])].erase (pos);
s1[lca (val, a[pos + 1])].insert (pos);
}
a[pos] = val;
}
else {
int l, r, val;
cin >> l >> r >> val;
auto tr = s[val].lower_bound (l);
if (tr != s[val].end()) {
int x = *tr;
if (x <= r) {
cout << x << " " << x << "\n";
continue;
}
}
tr = s1[val].lower_bound (l);
if (tr != s1[val].end()) {
int x = *tr;
if (x < r) {
cout << x << " " << x + 1 << "\n";
continue;
}
}
cout << "-1 -1\n";
}
}
}
# | 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... |