Author: Dong Liu

# 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.

C++

Time complexity: $\mathcal O(N\log^2 N)$

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


### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!