  Social distance games have been extensively studied as a coalition formation
model where the utilities of agents in each coalition were captured using a
utility function $u$ that took into account distances in a given social
network. In this paper, we consider a non-normalized score-based definition of
social distance games where the utility function $u^s$ depends on a generic
scoring vector $s$, which may be customized to match the specifics of each
individual application scenario.
  As our main technical contribution, we establish the tractability of
computing a welfare-maximizing partitioning of the agents into coalitions on
tree-like networks, for every score-based function $u^s$. We provide more
efficient algorithms when dealing with specific choices of $u^s$ or simpler
networks, and also extend all of these results to computing coalitions that are
Nash stable or individually rational. We view these results as a further strong
indication of the usefulness of the proposed score-based utility function: even
on very simple networks, the problem of computing a welfare-maximizing
partitioning into coalitions remains open for the originally considered
canonical function $u$.
