YS - Vertex Set Path Composite

Time Complexity: $\mathcal{O}(N \log^2 N)$ from HLD

Main Idea: Different from a classic HLD problem, the nesting of functions does not follow the commutative property. In other words, the answer of the query $1$ $u$ $v$ $x$ is different from the answer of the query $1$ $v$ $u$ $x$.

To solve this problem, we can break down the path from node $u$ to node $v$ into two paths: from node $u$ to $LCA(u,v)$ and from $LCA(u,v)$ to node $v$. The path from node $u$ to $LCA(u,v)$ will decrease in depth, and the path from $LCA(u,v)$ to node $v$ will increase in depth.

We can then maintain two segment trees.

The first segment tree will calculate the equivalent function that results from moving from node $u$ to $LCA(u,v)$. And the second segment tree will calculate the equivalent function that results from moving from $LCA(u,v)$ to node $v$. After this we can plug in the given $x$ into the two functions to get the answer of the query.

It should be mentioned that the function at node $LCA(u,v)$ should only be calculated once. To avoid calculating the node twice, we can intentionally avoid $LCA(u,v)$ during exactly one of the two path queries.

The update queries can be implemented using segment tree point updates on both segment trees.

Copy
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;

const int maxN = 2e5 + 5;
const int height = 25;