Link to this code:
https://cses.fi/paste/0294b268ed51c6625a2a9b/
/*
_ _
| |__ | |__ __ _ __ _ _ _ __ _
| '_ \| '_ \ / _` |/ _` | | | |/ _` |
| |_) | | | | (_| | (_| | |_| | (_| |
|_.__/|_| |_|\__,_|\__, |\__, |\__,_|
|___/ |___/
*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ppb pop_back
#define BigInt __int128
#define endl '\n'
#define mii map<ll int,ll int>
#define pii pair<ll int,ll int>
#define vi vector<ll int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define hell 1000000007
using namespace std;
#define N 200005
int arr[N];
int a[N],seg[N<<2];
void build(int node,int start,int end){
if(start==end){
seg[node]=a[start];
return;
}
int mid=(start+end)>>1;
build(node<<1,start,mid);
build(node<<1|1,mid+1,end);
seg[node]=max(seg[node<<1], seg[node<<1|1]);
}
int query(int node,int start,int end,int l,int r){
if(l<=start && r>=end) return seg[node];
if(r<start || l>end) return 0;
int mid=(start+end)>>1;
int ans1=query(node<<1,start,mid,l,r);
int ans2=query(node<<1|1,mid+1,end,l,r);
return max(ans1,ans2);
}
void update(int node,int start,int end,int x,int val){
if(start==end){
a[x]=val;
seg[node]=val;
return;
}
int mid=(start+end)>>1;
if(start<=x && x<=mid) update(node<<1,start,mid,x,val);
else update(node<<1|1,mid+1,end,x,val);
seg[node]=max(seg[node<<1], seg[node<<1|1]);
}
class HeavyLight {
struct Node {
int jump, subsize, depth, lin, parent;
vector<int> leg;
};
vector<Node> T;
bool processed = false;
public:
HeavyLight(int n) : T(n) {}
void AddEdge(int a, int b) {
T[a].leg.push_back(b);
T[b].leg.push_back(a);
}
void Preprocess() {
dfs_sub(0, -1);
dfs_jump(0, 0);
processed = true;
}
// Gets the position in the HL linearization
int GetPosition(int node) {
assert(processed);
return T[node].lin;
}
// Gets an array of ranges of form [li...ri)
// that correspond to the ranges you would need
// to query in the underlying structure
vector<pair<int, int>> GetPathRanges(int a, int b) {
assert(processed);
vector<pair<int, int>> ret;
while (T[a].jump != T[b].jump) {
if (T[T[a].jump].depth < T[T[b].jump].depth)
swap(a, b);
ret.emplace_back(T[T[a].jump].lin, T[a].lin + 1);
a = T[T[a].jump].parent;
}
if (T[a].depth < T[b].depth) swap(a, b);
ret.emplace_back(T[b].lin, T[a].lin + 1);
return ret;
}
private:
int dfs_sub(int x, int par) {
auto &node = T[x];
node.subsize = 1;
node.parent = par;
if (par != -1) {
node.leg.erase(find(node.leg.begin(), node.leg.end(), par));
node.depth = 1 + T[par].depth;
}
for (auto vec : node.leg)
node.subsize += dfs_sub(vec, x);
return node.subsize;
}
int timer = 0;
void dfs_jump(int x, int jump) {
auto &node = T[x];
node.jump = jump;
node.lin = timer++;
iter_swap(node.leg.begin(), max_element(node.leg.begin(), node.leg.end(),
[&](int a, int b) { return T[a].subsize < T[b].subsize; }));
for (auto vec : node.leg)
dfs_jump(vec, vec == node.leg.front() ? jump : vec);
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int TESTS=1;
// cin>>TESTS;
while(TESTS--)
{
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
}
HeavyLight graph(n);
int m = n - 1;
while(m--) {
int x, y;
cin >> x >> y;
x--;y--;
graph.AddEdge(x, y);
}
graph.Preprocess();
int maxi = 0;
for(int i = 1; i <= n; i++) {
int idx = graph.GetPosition(i - 1) + 1;
maxi = max(maxi, idx);
a[idx] = arr[i];
}
build(1, 1, maxi);
while(q--) {
int t;
cin >> t;
if(t == 1) {
int i, x;
cin >> i >> x;
int idx = graph.GetPosition(i - 1) + 1;
update(1, 1, maxi, idx, x);
}
else {
int a, b;
cin >> a >> b;
a--;b--;
vector<pair<int, int>> v = graph.GetPathRanges(a, b);
int ans = 0;
for(auto path : v) {
ans = max(ans, query(1, 1, maxi, path.F + 1, path.S));
}
cout << ans << " ";
}
}
}
return 0;
}