#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 1,MOD = 998244353;
int n,m,q,a[N],up[N][25],tin[N],tout[N],timer = 0,b[N];
vector<int> g[N];
multiset<pair<int,int>> s[N * 4],t[N * 4];
pair<int,int> cur,cur1;
void dfs(int v,int pr = 1){
tin[v] = ++timer;
up[v][0] = pr;
for(int i = 1;i <= 20;i++){
up[v][i] = up[up[v][i - 1]][i - 1];
}
for(int to:g[v]){
if(to != pr) dfs(to,v);
}
tout[v] = timer;
}
bool is(int v,int u){
return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int lca(int v,int u){
if(is(v,u)) return v;
if(is(u,v)) return u;
for(int i = 18;i >= 0;i--){
if(!is(up[v][i],u)){
v = up[v][i];
}
}
return up[v][0];
}
void build(int v = 1,int tl = 1,int tr = m - 1){
if(tl == tr){
s[v].insert(make_pair(b[tl],tl));
}else{
int tm = (tl + tr) >> 1;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
s[v] = s[v + v];
for(auto k:s[v + v + 1]){
s[v].insert(k);
}
}
}
void build1(int v = 1,int tl = 1,int tr = m){
if(tl == tr){
t[v].insert({a[tl],tl});
}else{
int tm = (tl + tr) >> 1;
build(v + v,tl,tm);
build(v + v + 1,tm + 1,tr);
t[v] = t[v + v];
for(auto k:t[v + v + 1]){
t[v].insert(k);
}
}
}
void upd1(int pos,int val,int v = 1,int tl = 1,int tr = m){
t[v].erase({a[pos],pos});
t[v].insert({val,pos});
if(tl == tr) return;
int tm = (tl + tr) >> 1;
if(pos <= tm) upd1(pos,val,v+v,tl,tm);
else upd1(pos,val,v+v+1,tm+1,tr);
}
bool find1(int l,int r,int val,int v = 1,int tl = 1,int tr = m){
if(tl > r || l > tr || l > r) return false;
if(tl >= l && tr <=r){
auto it = t[v].lower_bound({val,0});
if(it == t[v].end()) return false;
if((*it).first != val) return false;
cur1 = *it;
return 1;
}else{
int tm = (tl + tr) >> 1;
return (find1(l,r,val,v+v,tl,tm) | find1(l,r,val,v+v+1,tm+1,tr));
}
}
void upd(int pos,int val,int v = 1,int tl = 1,int tr = m - 1){
s[v].erase({b[pos],pos});
s[v].insert({val,pos});
if(tl == tr) return;
int tm = (tl + tr) >> 1;
if(pos <= tm) upd(pos,val,v+v,tl,tm);
else upd(pos,val,v+v+1,tm+1,tr);
}
bool find(int l,int r,int val,int v = 1,int tl = 1,int tr = m-1){
if(tl > r || l > tr || l > r) return false;
if(tl >= l && tr <=r){
auto it = s[v].lower_bound({val,0});
if(it == s[v].end()) return false;
if((*it).first != val) return false;
cur = *it;
return 1;
}else{
int tm = (tl + tr) >> 1;
return (find(l,r,val,v+v,tl,tm) | find(l,r,val,v+v+1,tm+1,tr));
}
}
void test(){
cin >> n >> m >> q;
for(int i = 1;i <= n - 1;i++){
int x,y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1);
for(int i = 1;i <= m;i++){
cin >> a[i];
if(i > 1) b[i - 1] = lca(a[i - 1],a[i]);
}
if(m > 1) build();
while(q--){
int tp;
cin >> tp;
if(tp == 1){
int pos,v;
cin >> pos >> v;
if(pos < m){
int x = lca(v,a[v + 1]);
upd(pos,x);
b[pos] = x;
}
if(pos > 1){
int x = lca(a[pos - 1],v);
upd(pos - 1,x);
b[pos - 1] = x;
}
upd1(pos,v);
a[pos] = v;
}else{
int l,r,v;
cin >> l >> r >> v;
if(l == r){
if(v == a[l]){
cout << l << ' ' << r << '\n';
}else{
cout << -1 << ' ' << -1 << '\n';
}
continue;
}
if(find(l,r - 1,v)){
cout << cur.second << ' ' << cur.second + 1 << '\n';
}else{
if(find1(l,r,v)){
cout << cur1.second << ' ' << cur1.second << '\n';
continue;
}
cout << -1 << ' ' << -1 << '\n';
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--) test();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
80148 KB |
n=5 |
| 2 |
Incorrect |
36 ms |
80188 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
80148 KB |
n=5 |
| 2 |
Incorrect |
36 ms |
80188 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
80148 KB |
n=5 |
| 2 |
Incorrect |
36 ms |
80188 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
80148 KB |
n=5 |
| 2 |
Incorrect |
36 ms |
80188 KB |
Jury has the answer but participant has not |
| 3 |
Halted |
0 ms |
0 KB |
- |
