#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 2e5 + 5;
const int MOD = 1e9 + 7;
int n, m, q, lvl[N], tin[N], tout[N], timer;
vector<int> graph[N];
vector<vector<int> > dp(N, vector<int>(20, -1));
void dfs(int source, int par, int level){
dp[source][0] = par;
lvl[source] = level;
tin[source] = ++timer;
for(auto k : graph[source])
if(k != par)
dfs(k, source, level + 1);
tout[source] = ++timer;
}
void init(){
dfs(1, -1, 0);
for(int i = 1; i <= (log2(n)); ++i)
for(int j = 1; j <= n; ++j)
if(dp[j][i - 1] != -1)
dp[j][i] = dp[dp[j][i - 1]][i - 1];
}
ll LCA(int u, int v){
if(lvl[u] > lvl[v]) swap(u, v);
ll d = lvl[v] - lvl[u];
while(d){
int jump = log2(d);
v = dp[v][jump];
d -= pow(2, jump);
}
if(v == u)
return v;
for(int i = log2(n); i >= 0; --i){
if(dp[v][i] != -1 && dp[v][i] != dp[u][i]){
u = dp[u][i];
v = dp[v][i];
}
}
return dp[v][0];
}
void solve(){
cin >> n >> m >> q;
vector<int> seq;
for(int i = 0; i < n - 1; ++i){
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for(int i = 0; i < m; ++i){
int x;
cin >> x;
seq.push_back(x);
}
init();
while(q--){
int query;
cin >> query;
if(query == 1){
int x, val;
cin >> x >> val;
--x;
seq[x] = val;
}
else{
int l, r, v;
cin >> l >> r >> v;
--l, --r;
bool ok = 0;
int cur = -1, pre = -1;
for(int i = 0; i < seq.size(); ++i){
int x = seq[i];
if(tin[x] >= tin[v] and tout[x] <= tout[v]){
if(cur == -1){
cur = x;
pre = i;
}else cur = LCA(cur, x);
}
else{
cur = -1;
pre = -1;
}
if(cur == v){
cout << pre + 1 << ' ' << i + 1 << '\n';
ok = 1;
break;
}
}
if(!ok) cout << "-1 -1\n";
}
}
}
int main(){
fast;
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
Compilation message
treearray.cpp: In function 'void solve()':
treearray.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i = 0; i < seq.size(); ++i){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
28496 KB |
Wrong output format. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
28496 KB |
Wrong output format. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
28496 KB |
Wrong output format. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
28496 KB |
Wrong output format. |
| 2 |
Halted |
0 ms |
0 KB |
- |
