#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
using namespace std;
ll in[200020],l,r,n,m,xx,yy,q,a[200020],type,pa;
ll out[200020];
ll timer=1;
ll P[200020][18];
vector<ll>v[200005],g;
void dfs(int p,int u) {
P[u][0]=p;
for (int i=1;i<=17;i++)
P[u][i]=P[P[u][i-1]][i-1];
timer++;
in[u]=timer;
for (int i=0;i<v[u].size();i++)
if (v[u][i] != p){
dfs(u,v[u][i]);
}
out[u]=timer;
}
int lca(int a,int b) {
if (in[a] <= in[b] && out[b] <= out[a]) return a;
for (int i=17;i>=0;i--)
if (P[a][i])
if (!(in[P[a][i]] <= in[b] && out[b] <= out[P[a][i]]))
a=P[a][i];
return P[a][0];
}
set<ll>st[200005],st1[200005],st2[200005];
int main(){
cin >> n >> m >> q;
for(int i=1; i<n; i++){
cin >> xx >> yy;
v[xx].pb(yy);
v[yy].pb(xx);
}
dfs(1,1);
for(int i=1; i<=m; i++){
cin >> a[i];
}
for(int i=1; i<=m; i++){
xx = i;
yy = a[i];
st[yy].insert(xx);
if(xx != 1){
ll pp = lca(a[xx],a[xx-1]);
pp = lca(yy,a[xx-1]);
st1[pp].insert(xx-1);
}
if(xx != m){
ll pp = lca(a[xx],a[xx+1]);
pp = lca(yy,a[xx+1]);
st2[pp].insert(xx+1);
}
a[xx] = yy;
}
while(q--){
cin >> type;
if(type == 1){
cin >> xx >> yy;
st[a[xx]].erase(st[a[xx]].find(xx));
st[yy].insert(xx);
if(xx != 1){
ll pp = lca(a[xx],a[xx-1]);
st1[pp].erase(st1[pp].find(xx-1));
st2[pp].erase(st2[pp].find(xx));
pp = lca(yy,a[xx-1]);
st1[pp].insert(xx);
}
if(xx != m){
ll pp = lca(a[xx],a[xx+1]);
st2[pp].erase(st2[pp].find(xx+1));
st1[pp].erase(st1[pp].find(xx));
pp = lca(yy,a[xx+1]);
st2[pp].insert(xx);
}
a[xx] = yy;
}
else {
cin >> l >> r >> pa;
if(st[pa].lower_bound(l) != st[pa].end()){
if(*(st[pa].lower_bound(l)) <= r){
cout << *(st[pa].lower_bound(l)) << " " << *(st[pa].lower_bound(l)) << endl;
continue;
}
}
if(st2[pa].lower_bound(l+1) != st2[pa].end()){
if(*(st2[pa].lower_bound(l+1)) <= r){
cout << *(st2[pa].lower_bound(l+1)) - 1<< " " << *(st2[pa].lower_bound(l+1)) << endl;
continue;
}
}
if(st1[pa].lower_bound(l) != st1[pa].end()){
if(*(st1[pa].lower_bound(l)) < r){
cout << *(st1[pa].lower_bound(l))<< " " << *(st1[pa].lower_bound(l)) + 1<< endl;
continue;
}
}
cout <<"-1 -1\n";
}
}
return 0;
}
Compilation message
treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<v[u].size();i++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
33272 KB |
n=5 |
| 2 |
Runtime error |
68 ms |
66556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
33272 KB |
n=5 |
| 2 |
Runtime error |
68 ms |
66556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
33272 KB |
n=5 |
| 2 |
Runtime error |
68 ms |
66556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
33272 KB |
n=5 |
| 2 |
Runtime error |
68 ms |
66556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
