Jumping Man

Reframe the Beast

For a fixed node $i$, we have a multiset of strings produced by all valid descending paths fully inside $sub(i)$. We need

$$\sum_s cnt_i(s)^2.$$

That is the number of ordered pairs of paths inside $sub(i)$ that produce the same string. This is the main de-bullshit step. We do not need to store strings, hash strings, build a trie, or summon suffix-array dark magic.

A valid path is just a nonempty chain in the ancestor order:

$$x_1, x_2, \ldots, x_k$$

where each next node is a strict descendant of the previous one. Jumps can skip levels.

So for two paths to produce the same string, they must have the same length and matching letters position by position.

Pair DP

Let

$$dp[u][v]$$

be the number of ordered pairs of valid paths that start exactly at nodes $u$ and $v$ and produce equal strings.

If $c_u \ne c_v$, then no equal string can start there:

$$dp[u][v]=0.$$

If $c_u=c_v$, then the first characters match. After that, there are two choices:

1. Stop both paths immediately. That contributes $1$.
2. Continue both paths by jumping from $u$ to some strict descendant $x$, and from $v$ to some strict descendant $y$. Then the number of valid suffix-pairs is $dp[x][y]$.

Therefore:

$$dp[u][v]=[c_u=c_v]\left(1+\sum_{x\in sub(u),\ x\ne u}\sum_{y\in sub(v),\ y\ne v} dp[x][y]\right).$$

This recurrence is clean, but a direct implementation would be way too slow: four nested subtree loops, aka performance murder with paperwork.

Euler Tour Saves the Day

Root the tree at $1$. Run DFS and assign each node a time $tin[u]$ such that every subtree is a contiguous interval:

$$sub(u) = [tin[u], tout[u]].$$

Now the sum

$$\sum_{x\in sub(u),\ x\ne u}\sum_{y\in sub(v),\ y\ne v} dp[x][y]$$

is just a rectangle sum over the matrix $dp$ in Euler order:

$$[tin[u]+1, tout[u]] \times [tin[v]+1, tout[v]].$$

Why $tin[u]+1$? In DFS preorder, the root of the subtree is first, so all strict descendants of $u$ occupy exactly the rest of that subtree interval.

Nice. Now we just need rectangle sums of already-computed $dp$ values.

Order of Computation

The recurrence for $dp[u][v]$ only uses $dp[x][y]$ where $x$ is a strict descendant of $u$ and $y$ is a strict descendant of $v$.

So if we process nodes in reverse Euler order, descendants are already done. For pairs, process Euler indices from $n$ down to $1$ in both dimensions. When computing the cell $(a,b)$, every cell inside the descendant rectangle has larger Euler indices, so it is already known.

Let $node[pos]$ be the node at Euler position $pos$.

We maintain a 2D suffix-sum table over the Euler matrix:

$$suf[i][j] = \sum_{x\ge i}\sum_{y\ge j} mat[x][y],$$

where

$$mat[tin[u]][tin[v]] = dp[u][v].$$

A rectangle sum is then:

$$rect(x_1,y_1,x_2,y_2)=suf[x_1][y_1]-suf[x_2+1][y_1]-suf[x_1][y_2+1]+suf[x_2+1][y_2+1].$$

When we fill cells from bottom-right to top-left, we can compute suf[i][j] immediately after computing mat[i][j]:

$$suf[i][j]=mat[i][j]+suf[i+1][j]+suf[i][j+1]-suf[i+1][j+1].$$

So each $dp$ cell is computed in $O(1)$.

Getting the Final Answers

For node $i$, we need all ordered path pairs whose first nodes are both inside $sub(i)$:

$$ans[i]=\sum_{u\in sub(i)}\sum_{v\in sub(i)} dp[u][v].$$

That is another rectangle sum over $mat$:

$$[tin[i], tout[i]] \times [tin[i], tout[i]].$$

Use the same suffix table. Done.

Correctness Proof

We prove the algorithm computes every answer correctly.

First, consider $dp[u][v]$. If $c_u\ne c_v$, no pair of paths starting at $u$ and $v$ can produce equal strings, because their first characters already differ. The algorithm sets $dp[u][v]=0$, which is correct.

Now suppose $c_u=c_v$. Any equal-string pair of paths starting at $u$ and $v$ has matching first characters. After that, exactly one of two things happens: both paths stop, producing the one-character string, or both continue. They cannot have only one path continue, because then the string lengths would differ. If they continue, the first jumps must go to some strict descendants $x$ of $u$ and $y$ of $v$, and the remaining suffixes must be an equal-string path pair starting at $(x,y)$. There are $dp[x][y]$ such suffix-pairs. These choices are disjoint and cover all possibilities, so the recurrence is exact.

The computation order is valid because $dp[u][v]$ only depends on pairs $(x,y)$ where both nodes are strict descendants. In Euler preorder, strict descendants of a node appear later inside its subtree interval. Processing Euler positions in decreasing order guarantees all needed descendant-pair values are already computed.

The suffix-sum table correctly returns sums over any rectangle of the Euler-indexed $dp$ matrix by the standard 2D inclusion-exclusion formula. Therefore the algorithm computes each recurrence value exactly.

Finally, for a fixed subtree root $i$, every generated path starts at exactly one node $u\in sub(i)$. Thus every ordered pair of generated paths corresponds to exactly one ordered pair of starting nodes $(u,v)$ inside $sub(i)$, and contributes to $dp[u][v]$ precisely when the produced strings are equal. Summing $dp[u][v]$ over all $u,v\in sub(i)$ therefore equals $\sum_s cnt_i(s)^2$. That is exactly the requested answer.

Complexity

There are $n^2$ pairs of nodes. Each pair is processed in $O(1)$ using rectangle sums.

So each test case runs in

$$O(n^2)$$

time and uses

$$O(n^2)$$

memory. Since $\sum n\le 5000$, this fits comfortably. Not free, but definitely not cursed.