Let $T$ be a tree, and there is a weight function on the edges $w:E\to X$. $(X,\oplus)$ is a monoid structure.Define $f(u,v) = \bigoplus_{i=1}^k w(e_i)$, where $e_1,\ldots,e_k$ is the unique path from $u$ to $v$.Can we preprocess the tree, such that we can use linear space (or close to linear space), so we can answer queries $f(u,v)$ in $O(\mathrm{polylog} (n))$ monoid operations? The problem become more interesting if we allow removing edges and add edge between two vertices in distinct trees.We can also ask the question on a DAG, with weights from a commutative monoid. We want to preprocess in linear time, and query the result of $f(u,v)= \sum_{e} w(e)$, where $e$ is in some path from $u$ to $v$, in $O(\mathrm{polylog} (n))$ time.If we consider the very special case where the entire graph is just a path, then what we want is a dynamic version of a Fenwick tree. A finger tree can solve the problem in $O(\log n)$ time.
Data structure for finding the sum of edge weights on a path
data structures;graphs