Ensemble of tree decompositions for all-pairs problem
I would simply do as follows:

Start with a tree decomposition $T$ of $G$. Each time you would like to compute the number of self avoiding walks on $G$ passing through $u$ and some other node, do dynamic programming on the tree decomposition $T&#39;$ obtained from $T$ by adding $u$ to each bag of the tree decomposition. The width of $T&#39;$ is at most the width of $T$ plus one, and you cannot hope for anything better in general.