Solution

This problem can solved with Heavy Light Decomposition; we can label each edge as either heavy or light. We can use a segment tree to keep track of the maximum value in each heavy chain.

Now, to change the value at node $i$ to $x$, we can just update the value in the segment tree. To query the maximum value in the path from $a$ to $b$, we first find the Lowest Common Ancestor. We combine the path from $a$ to $lca(a,b)$ and the path from $b$ to $lca(a,b)$ to find our answer.

Copy
#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];