//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 2e5 + 12;
vt<int> g[maxn];
set<int> nei[maxn], sing[maxn];
int dp[maxn], up[maxn][20], a[maxn];
void dfs(int v){
for(auto i : g[v]){
if(up[v][0] == i)continue;
dp[i] = dp[v] + 1;
up[i][0] = v;
dfs(i);
}
}
int lca(int x, int y){
if(dp[x] > dp[y])swap(x, y);
int k = dp[y] - dp[x], o = 0;
while(k){
if(k & 1)y = up[y][o];
o++;
k >>= 1;
}
if(x == y)return x;
for(int i = 19; i >= 0; i--){
if(up[x][i] != up[y][i]){
x = up[x][i], y = up[y][i];
}
}
return up[x][0];
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
for(int i = 0, u, v; i < n - 1; i++){
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
up[1][0] = 1;
dfs(1);
for(int i = 1; i < 20; i++){
for(int j = 1; j <= n; j++)up[i][j] = up[up[i - 1][j]][j];
}
for(int i = 1; i <= m; i++){
cin >> a[i];
sing[a[i]].insert(i);
if(i > 1){
nei[lca(a[i], a[i - 1])].insert(i - 1);
}
}
for(int i = 0; i < q; i++){
int w;
cin >> w;
if(w == 1){
int pos, v, head;
cin >> pos >> v;
if(pos > 1){
head = lca(a[pos - 1], a[pos]);
nei[head].erase(pos - 1);
head = lca(a[pos - 1], v);
nei[head].insert(pos - 1);
}
if(pos < m){
head = lca(a[pos], a[pos + 1]);
nei[head].erase(pos);
head = lca(v, a[pos + 1]);
nei[head].insert(pos);
}
sing[a[pos]].erase(pos);
a[pos] = v;
sing[a[pos]].insert(pos);
}
else {
int l, r, x;
cin >> l >> r >> x;
if(sing[x].lower_bound(l) != sing[x].end() && *sing[x].lower_bound(l) <= r){
cout << *sing[x].lower_bound(l) << ' ' << *sing[x].lower_bound(l) << '\n';
}
else if(nei[x].lower_bound(l) != nei[x].end() && *nei[x].lower_bound(l) < r){
cout << *nei[x].lower_bound(l) << ' ' << *nei[x].lower_bound(l) + 1 << '\n';
}
else cout << "-1 -1\n";
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int times = 1;
//cin >> times;
for(int i = 1; i <= times; i++) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
24408 KB |
n=5 |
| 2 |
Incorrect |
7 ms |
24412 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
24408 KB |
n=5 |
| 2 |
Incorrect |
7 ms |
24412 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
24408 KB |
n=5 |
| 2 |
Incorrect |
7 ms |
24412 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
24408 KB |
n=5 |
| 2 |
Incorrect |
7 ms |
24412 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
