diff options
| -rw-r--r-- | mgr.tex | 18 |
1 files changed, 10 insertions, 8 deletions
@@ -703,14 +703,16 @@ the root vertices of each such component), call this data $\componenttable[x.q]$. For each color $c$, we will preprocess the above graph for answering questions -of the form ``if we start in a vertex $z.q$ colored with $c$, which is the first -copy of $Q$ on the path towards the copy of $Q$ that contains $y$?''. To achieve -this, we create a copy of $T$ in which we mark the vertices where an edge from a -$c$-colored vertex points to a vertex with a lower color. This tree we -preprocess for highest marked descendant on path questions, solved in the -previous section. Note that Figure \ref{marked-figure} is exactly the marked -tree we create and preprocess for the green color of the colored graph in Figure -\ref{tree-figure}. +of the form ``given a vertex $z.q$ colored with $c$, which is the first copy of +$Q$ on the path towards the copy of $Q$ that contains $y$ where the path from +$z.q$ changes color?''. To achieve this, we create a copy of $T$ with a newly +added root (thus this tree's vertices correspond to copies of $Q$ in our +fattened tree) in which we mark the vertices corresponding to copies of $Q$ +where a non-$c$-colored vertex is pointed to by an edge from a $c$-colored +vertex in the parent copy of $Q$. This tree we preprocess for highest marked +descendant on path questions, solved in the previous section. Note that Figure +\ref{marked-figure} is exactly the marked tree we create and preprocess for the +green color of the colored graph in Figure \ref{tree-figure}. Now question answering can proceed similar to the word case. Given a question ``does the word on vertices from $x$ down to $y$ belong to $L$?'', let $x'$ be |