Let $k$ be the value where we wrap around, in this case $10$. Then the problem can be solved in $\mathcal{O}(n^2 k^2)$ with DP. With some tricks we will improve this to $\mathcal{O}(n k^2 \log n)$. For fixed $k$ this complexity is nearly linear, $\mathcal{O}(n \log n)$. Both algorithms work even on worst-case inputs: the assumption of random assignment of values is unnecessary.
We start from the $\mathcal{O}(n^2 k^2)$ algorithm. A connected graph with $n$ vertices and $n-1$ edges is a tree. To check if we can start from some vertex $r$, root the tree at that vertex. We will store the dp states $DP[i][t]$, which will denote if the subtree of vertex $i$ can be made to contain only the value $k$, if we cross the edge between $i$ and its parent $t$ times $(\text{mod}\ 2k)$, and our path starts from an ancestor of $i$. After calculating the $DP$, we know that the path may begin from $r$ iff $DP[r][2k-1] = 1$.
Note that we may assume that all edges are traversed at least once, since traversing any path back and forth $k$ times changes nothing. Additionally, crossing some edge $2k$ more or less times doesn't change whether a solution exists as long as we still cross it at least once, as we can re-connect the tours visiting these vertices such that we get a path that visits every vertex the same amount of times $(\text{mod}\ k)$.
Let $C_{i, j}$ denote the $j$th child of vertex $i$. Let $V_i$ denote the number of times we have to visit the vertex $(\text{mod}\ k)$ for its value to equal $k$. We have the requrrences
\begin{gather}
DP[i][2t_0] = \max_{\sum_{j} t_j = V_i\ (\text{mod}\ k)} \min_{j = 1, \dots, |C_i|}DP[C_{i, j}][2t_j]\\
DP[i][2t_0 - 1] = \max_{\sum_{j} t_j = V_i\ (\text{mod}\ k)} \max_{r = 0, \dots, |C_i|} \min_{j = 1, \dots, |C_i|}DP[C_{i, j}][2t_j + \mathbb{I}_{r}(j)]
\end{gather}
where $\mathbb{I}_{r}(j) = 1$ iff $r = j$.
The first recurrence holds, since if we cross the edge from $i$ to its parent $2t_0$ times and the edge from $i$ to its $j$th child $2t_j$ times, we visit $i$ exactly $\sum_j t_j$ times, which must equal $V_i\ (\text{mod}\ k)$. On the other hand, since the edges crossed an odd number of times form a path starting from $r$, and we cross the edge from $i$ to its parent an even number of times, we must likewise cross the edges from $i$ to its children an even number of times.
The second recurrence similarly holds, since if we cross the edge from $i$s parent to $i$ $2t_0 - 1$ times, $t_0$ of those crossings end in $i$, and if we cross the edge from $i$ to its $j$th child $2t_j + 1$ times, $t_j$ of those crossings end in $i$. Thus this sum must equal $V_i\ (\text{mod}\ k)$. The same path argument gives us that we may cross at most one edge from $i$ to its children an odd number of times.
These recurrences can be computed in $\mathcal{O}(|C_i| k^2)$ by initialising $DP[i][t] = \mathbb{I}_{0}(t)$, then looping over the children, at child $j$ assigning
\begin{gather}
DP[i][2t-1] \gets \max_{0 \leq t_1 < 2k} \max_{r = 0, 1} \min(DP[i][2t - 2t_1 - r],\ DP[C_{i, j}][2t_1 + (1 - r)])\\
DP[i][2t] \gets \max_{0 \leq t_1 < 2k} \min(DP[i][2t - 2t_1],\ DP[C_{i, j}][2t_1])\\
\end{gather}
At this point, $DP[i][2t-r]$, for $r \in {0, 1}$, is one if we can visit $i$ in total $t$ times, crossing the edge from $i$s parent to $i$ exactly $-r$ times $(\text{mod}\ 2k)$, but we need the amount of visits to equal $V_i$, so we finally assign
\begin{gather}
DP[i][2t] \gets DP[i][2V_i - 2t]\\
DP[i][2t-1] \gets DP[i][2V_i - 2t - 1]\\
\end{gather}
The complexity of checking one $r$ is thus $\mathcal{O}(\sum_i |C_i| k^2) = \mathcal{O}(n k^2)$, giving the complexity $\mathcal{O}(n^2 k^2)$.
We can optimise this by noticing that we calculate the same $DP$ values multiple times. However, the straightforward approach of leveraging this fails: calculating $DP'[i][p][t]$, where $p$ is the neighbour of $i$ that is an ancestor of $i$ might take $\mathcal{O}(n^2 k^2)$ time, even though there are only $4(n-1)k$ states: consider the star graph. To fix this issue, we use centroid decomposition.
The centroid is a vertex of the tree, such that if we root the tree at that vertex, every subtree will have size at most $\frac{n}{2}$. Such a vertex always exists. Our algorithm will work as follows:
- Root the tree at the centroid $r$
- Calculate $DP'[C_{r,j}][i][t]$ for all $j, t$ in $\mathcal{O}(nk^{2})$. This gives us the answer for $r$
- Using these values, calculate $DP'[i][C_{r,j}][t]$ for all $j, t$ in $\mathcal{O}(|C_r| \log |C_r| k^2)$
- Disable vertex $r$ and recurse to the remaining subtrees. Whenever we try to visit vertex $r$, just return the already calculated $DP$ values.
Before addressing how to do step 3, we'll calculate the complexity of this approach. At the $m$th (0-indexed) round, the size of every remaining subtree is at most $n2^{-m}$. Thus there are at most $\log n$ rounds. During the $m$th round, every remaining subtree is adjacent to at most $m \leq \log n$ already handled vertices. If $n_r$ is the size of the remaining subtree $r$ is in when $r$ is picked centroid, then steps 1-3 for that subtree take $\mathcal{O}((n_i + \log n) k^2 + |C_r| \log |C_r| k^2)$ time (due to the already handled at most $\log n$ vertices).
Since there are at most $\log n$ rounds, and the sum of $n_r$ of $r$ participating in that round is at most $n$, we have $\sum_{i} n_i \leq n \log n$. Thus the total complexity is
\begin{equation}
\mathcal{O}(\sum_{i} n_i k^2 + k^2 \log n + |C_i| \log |C_i| k^2) = \mathcal{O}(n k^2 \log n)
\end{equation}
since each term sums to at most this.
It remains to show how to do step 3. Note that our approach to calculating $DP[i][t]$ doesn't care about the processing order of the children. Say $|C_r| = 2^{m}$. First, using our approach, calculate the intermediate values for children with index in $[1, 2^{m-1}]$ and in $[2^{m-1} + 1, 2^{m}]$. At the $s$th (1-indexed) step, using the previously calculated values, calculate the values for children with index not in $[x 2^{m-s} + 1, (x+1) 2^{m-s}]$, for all $x$, in $\mathcal{O}(2^{m-s} k^2)$ time per interval (by including the other $2^{m-s}$ indices not in this inteval but in the interval in the previous step containing this interval). After the last step, we get $DP'[C_{r, j}][r]$ from the intermediate value for all children but $C_{r, j}$. This is indeed $\mathcal{O}(|C_r| \log |C_r| k^2)$.
