//bit chass 1
#include <bits/stdc++.h>
#define x first
#define y second
#define el "\n"
#define ll long long
#define pb push_back
#define pll pair <ll, ll>
#define pii pair <int, int>
#define all(x) x.begin(), x.end()
#define lcm(x,y) x * y / __gcd(x, y)
#define ibase ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
const int N = 2e5 + 5, inf = 1e9 + 7, M = 2e6, MM = 2e6 + 5, K = 300;
const ll MI = 2e18, mm = 1e15;
const double P = 3.14;
vector <int> g[N];
int tim, tin[N], tout[N], u[N][22], a[N];
set <int> s[N];
void dfs(int v, int pr) {
tin[v] = ++tim;
u[v][0] = pr;
for (int i = 1; i < 22; i++)
u[v][i] = u[u[v][i - 1]][i - 1];
for (int to : g[v]) {
if (to != pr)
dfs(to, v);
}
tout[v] = ++tim;
}
bool upper(int x, int y) {
return (tin[x] <= tin[y] && tin[y] <= tout[x]);
}
int lca(int x, int y) {
if (upper(x, y))
return x;
if (upper(y, x))
return y;
for (int i = 21; i >= 0; i--)
if (u[x][i] != 0 && !upper(u[x][i], y))
x = u[x][i];
return u[x][0];
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 1, x, y; i < n; i++) {
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
dfs(1, 0);
for (int i = 1; i <= m; i++) {
cin >> a[i];
s[a[i]].insert(i);
if (i > 1)
s[lca(a[i], a[i - 1])].insert(i - 1);//, cout << lca(a[i], a[i - 1]) << ' ' << i - 1 << ' ' << i << el;
}
// exit(0);
// for (int i = 1; i <= m; i++) {
// cout << i << ':' << el;
// for (auto j : s[i])
// cout << j.x << ' ' << j.y << ' ';
// cout << el;
// }
// exit(0);
for (int i = 1; i <= q; i++) {
int tp;
cin >> tp;
if (tp == 1) {
int pos, v;
cin >> pos >> v;
if (s[lca(a[pos], a[pos - 1])].lower_bound(pos - 1) != s[lca(a[pos], a[pos - 1])].end())
s[lca(a[pos], a[pos - 1])].erase(s[lca(a[pos], a[pos - 1])].lower_bound(pos - 1));
if (s[lca(a[pos], a[pos + 1])].lower_bound(pos) != s[lca(a[pos], a[pos + 1])].end())
s[lca(a[pos], a[pos + 1])].erase(s[lca(a[pos], a[pos + 1])].lower_bound(pos));
s[a[pos]].erase(s[a[pos]].lower_bound(pos));
if (pos != 1)
s[lca(a[pos - 1], v)].insert(pos - 1);
if (pos != m)
s[lca(a[pos + 1], v)].insert(pos);
s[v].insert(pos);
a[pos] = v;
}
else {
int l, r, v;
cin >> l >> r >> v;
auto tl = s[v].lower_bound(l);
if (tl != s[v].end() && *tl < r)
cout << *tl << ' ' << *tl + 1 << el;
else if (tl != s[v].end() && *tl == r && a[r] == v)
cout << *tl << ' ' << *tl << el;
else
cout << "-1 -1" << el;
}
}
}
int main() {
// ibase;
int T = 1;
// cin >> T;
for (int i = 1; i <= T; i++) {
// cout << "Case " << i << ": ";
solve();
cout << el;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14284 KB |
n=5 |
| 2 |
Incorrect |
7 ms |
14412 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14284 KB |
n=5 |
| 2 |
Incorrect |
7 ms |
14412 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14284 KB |
n=5 |
| 2 |
Incorrect |
7 ms |
14412 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14284 KB |
n=5 |
| 2 |
Incorrect |
7 ms |
14412 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
