#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct Tree{
int n, root;
vector<int> depth, head, sz, pa;
vector<int> f;
Tree(int n, int root, vector<vector<int>> &adj): n(n), root(root){
depth.resize(n+1, -1);
head.resize(n+1);
sz.resize(n+1, 0);
pa.resize(n+1, -1);
auto rootTree = [&](auto rootTree, int u, int p) -> void{
depth[u] = depth[p]+1;
pa[u] = p;
sz[u] = 1;
for(int v : adj[u]){
if(v == p) continue;
rootTree(rootTree, v, u);
sz[u] += sz[v];
}
};
rootTree(rootTree, root, 0);
auto decompose = [&](auto decompose, int u, int h) -> void{
head[u] = h;
int heavy = -1;
for(int v : adj[u]){
if(v == pa[u]) continue;
if(heavy == -1 || sz[heavy] < sz[v]) heavy = v;
}
if(heavy != -1) decompose(decompose, heavy, h);
for(int v : adj[u]){
if(v == pa[u] || v == heavy) continue;
decompose(decompose, v, v);
}
};
decompose(decompose, root, root);
f = [&]{
vector<array<int, 2>> first(n+1);
vector<array<int, 2>> second(n+1);
function<void(int, int)> dfs0 = [&](int u, int p) {
first[u] = second[u] = {0, -1};
for (int v : adj[u]) {
if (v == p) {
continue;
}
dfs0(v, u);
auto fetch = first[v];
fetch[0] += 1;
fetch[1] = v;
if (fetch > first[u]) {
swap(fetch, first[u]);
}
if (fetch > second[u]) {
swap(fetch, second[u]);
}
}
};
dfs0(1, 0);
function<void(int, int)> dfs = [&](int u, int p) {
for (int v : adj[u]) {
if (v == p) {
continue;
}
auto fetch = first[u][1] == v ? second[u] : first[u];
fetch[0] += 1;
fetch[1] = u;
if (fetch > first[v]) {
swap(fetch, first[v]);
}
if (fetch > second[v]) {
swap(fetch, second[v]);
}
dfs(v, u);
}
};
dfs(1, 0);
vector<int> f(n+1);
for (int u = 1; u <= n; u++) {
f[u] = first[u][0];
}
return f;
}();
};
int lca(int u, int v){
for(; head[u] != head[v]; v = pa[head[v]]){
if(depth[head[u]] > depth[head[v]]) swap(u, v);
}
if(depth[u] > depth[v]) swap(u, v);
return u;
}
int dist(int u, int v) {
return depth[u]+depth[v]-2*depth[lca(u, v)];
}
};
struct SegmentTree{
struct Node{
multiset<pair<int, int>> ms;
};
vector<Node> T;
int n, N;
SegmentTree(int n) : n(n){
N = 1;
while(N < n) N*=2;
T.resize(N*2+1, Node());
};
void upd(int i, pair<int, int> old, pair<int, int> nw){
auto ie = [&](Node &T, pair<int, int> old, pair<int, int> nw) -> void{
if(old.first != -1) T.ms.erase(T.ms.find(old));
T.ms.insert(nw);
};
auto upd = [&](auto upd, int node, int low, int high, int i, pair<int, int> old, pair<int, int> nw) -> void{
ie(T[node], old, nw);
if(low == high) return;
int mid = (low+high)/2;
if(i <= mid){
upd(upd, node*2, low, mid, i, old, nw);
}else{
upd(upd, node*2+1, mid+1, high, i, old, nw);
}
};
upd(upd, 1, 1, N, i, old, nw);
}
int query(int l, int r, int v){
if(l > r) return -1;
auto query = [&](auto self, int node, int low, int high, int l, int r, int v) -> int{
if(low > r || l > high) return -1;
if(low >= l && r >= high){
if((*T[node].ms.lower_bound({v, -1})).first != v) return -1;
return (*T[node].ms.lower_bound({v, -1})).second;
}
int mid = (low+high)/2;
int left = self(self, node*2, low, mid, l, r, v);
if(left != -1) return left;
return self(self, node*2+1, mid+1, high, l, r, v);
};
return query(query, 1, 1, N, l, r, v);
}
};
void solve(){
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> adj(n+1);
for(int i = 1; i < n; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> a(m+1);
for(int i = 1; i <= m; i++){
cin >> a[i];
}
SegmentTree T(m+1), T1(m+1);
Tree Y(n, 1, adj);
for(int i = 1; i <= m; i++){
T1.upd(i, {-1, -1}, {a[i], i});
if(i < m){
int lca = Y.lca(a[i], a[i+1]);
T.upd(i, {-1, -1}, {lca, i});
}
}
for(int i = 1; i <= q; i++){
int t, p, v, l, r;
cin >> t;
if(t == 1){
cin >> p >> v;
T1.upd(p, {a[p], p}, {v, p});
pair<int, int> old, nw;
if(p > 1){
old = {Y.lca(a[p-1], a[p]), p-1};
nw = {Y.lca(a[p-1], v), p-1};
T.upd(p-1, old, nw);
}
if(p < m){
old = {Y.lca(a[p+1], a[p]), p};
nw = {Y.lca(a[p+1], v), p};
T.upd(p, old, nw);
}
a[p] = v;
}else{
cin >> l >> r >> v;
int one = T1.query(l, r, v);
int two = T.query(l, r-1, v);
if(one != -1){
cout << one << " " << one;
}else if(two != -1){
cout << two << " " << two+1;
}else{
cout << "-1 -1\n";
}
cout << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
504 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
504 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
504 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
n=5 |
| 2 |
Incorrect |
2 ms |
504 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
