-
Notifications
You must be signed in to change notification settings - Fork 1
/
Path Queries II.cpp
103 lines (93 loc) · 1.84 KB
/
Path Queries II.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include "bits/stdc++.h"
using namespace std;
const int N = 2e5+5;
const int D = 19;
const int S = (1<<D);
int n, q, v[N];
vector<int> adj[N];
int sz[N], p[N], dep[N];
int st[S], id[N], tp[N];
void update(int idx, int val) {
st[idx += n] = val;
for (idx /= 2; idx; idx /= 2)
st[idx] = max(st[2 * idx], st[2 * idx + 1]);
}
int query(int lo, int hi) {
int ra = 0, rb = 0;
for (lo += n, hi += n + 1; lo < hi; lo /= 2, hi /= 2) {
if (lo & 1)
ra = max(ra, st[lo++]);
if (hi & 1)
rb = max(rb, st[--hi]);
}
return max(ra, rb);
}
int dfs_sz(int cur, int par) {
sz[cur] = 1;
p[cur] = par;
for(int chi : adj[cur]) {
if(chi == par) continue;
dep[chi] = dep[cur] + 1;
p[chi] = cur;
sz[cur] += dfs_sz(chi, cur);
}
return sz[cur];
}
int ct = 1;
void dfs_hld(int cur, int par, int top) {
id[cur] = ct++;
tp[cur] = top;
update(id[cur], v[cur]);
int h_chi = -1, h_sz = -1;
for(int chi : adj[cur]) {
if(chi == par) continue;
if(sz[chi] > h_sz) {
h_sz = sz[chi];
h_chi = chi;
}
}
if(h_chi == -1) return;
dfs_hld(h_chi, cur, top);
for(int chi : adj[cur]) {
if(chi == par || chi == h_chi) continue;
dfs_hld(chi, cur, chi);
}
}
int path(int x, int y){
int ret = 0;
while(tp[x] != tp[y]){
if(dep[tp[x]] < dep[tp[y]])swap(x,y);
ret = max(ret, query(id[tp[x]],id[x]));
x = p[tp[x]];
}
if(dep[x] > dep[y])swap(x,y);
ret = max(ret, query(id[x],id[y]));
return ret;
}
int main() {
scanf("%d%d", &n, &q);
for(int i=1; i<=n; i++) scanf("%d", &v[i]);
for(int i=2; i<=n; i++) {
int a, b;
scanf("%d%d", &a, &b);
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs_sz(1, 1);
dfs_hld(1, 1, 1);
while(q--) {
int t;
scanf("%d", &t);
if(t == 1) {
int s, x;
scanf("%d%d", &s, &x);
v[s] = x;
update(id[s], v[s]);
} else {
int a, b;
scanf("%d%d", &a, &b);
int res = path(a,b);
printf("%d\n ", res);
}
}
}