Denote generalized de Bruijn graph, where vertices’ string length is $n$, $B_n'$. Since there’s edge $(\alpha_i)_i \to (\beta_i)i$ iff $\forall 1 \le i \le n-1, \beta_i = \alpha{i+1}$, every vertex has indegree=outdegree=3. Therefore there is always Eulerian circuit in $B_n’$. Say there are digits on edges representing what digit to append. In the following, $n=3$.
Now for $B_{n-1}'$, take its Eulerian circuit, which consists of $3^{n-1}*3=3^n$ edges. Concatenating the digit on edges yields a cyclic arrangement of $3^n$ digits. Claim that all its $3^n$ (cyclic-)substrings of length n are all distinct.
Proof of claim: As the Eulerian circuit traverses on the graph, the last (cyclic-)substrings of length $n-1$ is exactly what written on the vertex. Every vertex v in $B_{n-1}'$ repeats exactly three times due to its indegree, and every v+(0/1/2), of length $n$, repeats exactly once, therefore all substrings of length n are distinct.
In this subcase, G is a tree.
For $uv \in E(G)$, WLOG let’s say u is the parent of v, then $s(u)-s(v)=size(v) - (n-size(v))=2*size(v) - n$, where $n=|V(G)|$, and $size(v)$ is the size of subtree of v.
Note that $s(u)-s(v) \ge 0$ iff $size(v) \ge n/2$. In a tree, all vertices that satisfy this condition must form a path from root to a vertex, say z. At first, pointer x points to the root. Moving x along the path leads to non-decreasing value of $s(x)$, while moving x from a vertex on path to any other vertex leads to strictly smaller $s(x)$.
Since the equaly sign will be achieved only at most once, $s(x)$ will mostly be increasing, except potentially when moving from $parent(z)$ to $z$. Then the barycenter either $z$ or $\{z, parent(z)\}$.
The center has distance to farthest vertex 5.
The barycenter is identified by the method in (a).
WOLG, $V(G)=V(K_n), E(G)=E(K_n)+(v_1,v_2)$, then the number of spanning tree of $G$ is the sum of the number of spanning tree of $K_n$ and the number of spanning tree of $K_n$ that contains $(v_1, v_2)$. The former is $n^{n-2}$.
For the latter, due to symmetry, the number of spanning tree of $K_n$ that contains $(x, y)$ should be the same for all $x \ne y$, say H. Iterating through all spanning tree and sum up this number essentially count every edge of each spanning tree exactly once. Therefore $H * {n \choose 2} = n^{n-2} * (n-1)$, thus $H=2 n^{n-3}$.
In total: $n^{n-2} + 2n^{n-3}$
According to Prüfer correspondence, we need to count the number of $(n-2)$-tuple $(a_1, a_2 \dots a_{n-2})$ that $\forall 1 \le i \le n-2, 1 \le i \le n$ and $| \{a_1 \dots a_{n-2}\} | = n-6$ and the number of occurance for any element is at most 2. Every such Prüfer code will corresponds to a valid tree, and they cover all of them.