CSES - Path Queries II

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 ii to xx, we can just update the value in the segment tree. To query the maximum value in the path from aa to bb, we first find the Lowest Common Ancestor. We combine the path from aa to lca(a,b)lca(a,b) and the path from bb to lca(a,b)lca(a,b) to find our answer.

C++

Time complexity: O(Nlog2N)\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!