#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define MOD (1e9+7)
#define all(x) x.begin(), x.end()
const int N = 1e6, K = 20;
int n, m, q, a[N], in[N], dp[N][K];
vector<int> g[N], euler;
set<pair<int, int>> v[N];
void dfs(int v, int p){
in[v] = euler.size();
euler.pb(v);
for(int u: g[v]){
if(u != p){
dfs(u, v);
euler.pb(v);
}
}
}
int lca(int a, int b){
a = in[a], b = in[b];
if(a > b) swap(a, b);
int k = int(log2(b-a+1));
int x = dp[a][k], y = dp[b - (1<<k) + 1][k];
return (in[x] < in[y] ? x : y);
}
void solve(){
cin >> n >> m >> q;
for(int i = 0; i < n - 1; ++i){
int u, v; cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
euler.pb(0);
dfs(1, 0);
for(int i = 1; i < euler.size(); ++i) dp[i][0] = euler[i];
for(int j = 1; j < K; ++j){
for(int i = 1; i + (1<<j) < euler.size() + 1; ++i){
int a, b;
a = dp[i][j - 1];
b = dp[i + (1<<(j-1))][j - 1];
if(in[a] < in[b])
dp[i][j] = a;
else
dp[i][j] = b;
}
}
for(int i = 1; i <= m; ++i) cin >> a[i];
for(int i = 1; i < m; ++i){
v[lca(a[i], a[i + 1])].insert({i, i + 1});
}
for(int i = 1; i <= m; ++i) v[a[i]].insert({i, i});
while(q--){
int tp; cin >> tp;
if(tp == 1){
int pos, u; cin >> pos >> u;
if(pos > 1){
int lc = lca(a[pos], a[pos - 1]);
v[lc].erase(make_pair(pos - 1, pos));
}
if(pos < m){
int lc = lca(a[pos], a[pos + 1]);
v[lc].erase(make_pair(pos, pos + 1));
}
v[u].erase(make_pair(pos, pos));
a[pos] = u;
if(pos > 1){
int lc = lca(a[pos], a[pos - 1]);
v[lc].insert(make_pair(pos - 1, pos));
}
if(pos < m){
int lc = lca(a[pos], a[pos + 1]);
v[lc].insert(make_pair(pos, pos + 1));
}
v[u].insert(make_pair(pos, pos));
}else{
int l, r, u; cin >> l >> r >> u;
auto it = v[u].lower_bound(make_pair(l, -1));
if(it == v[u].end() || (*it).second > r) cout << "-1 -1\n";
else cout << (*it).first << ' ' << (*it).second << '\n';
}
}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
solve();
return 0;
}
Compilation message
treearray.cpp: In function 'void solve()':
treearray.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 1; i < euler.size(); ++i) dp[i][0] = euler[i];
| ~~^~~~~~~~~~~~~~
treearray.cpp:46:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 1; i + (1<<j) < euler.size() + 1; ++i){
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
70764 KB |
n=5 |
| 2 |
Incorrect |
32 ms |
70692 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
70764 KB |
n=5 |
| 2 |
Incorrect |
32 ms |
70692 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
70764 KB |
n=5 |
| 2 |
Incorrect |
32 ms |
70692 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
70764 KB |
n=5 |
| 2 |
Incorrect |
32 ms |
70692 KB |
Wrong range. |
| 3 |
Halted |
0 ms |
0 KB |
- |
