CSES - Path Queries II
Author: Dong Liu
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 to , we can just update the value in the segment tree. To query the maximum value in the path from to , we first find the Lowest Common Ancestor. We combine the path from to and the path from to to find our answer.
#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!