Solution:
For convenience, let's first define some functions and variables:
- $len(i,j)$ represents the number of nodes visited from node $i$ to node $j$ along the entire path. For example, in Sample 1, $len(2,3)=3$, $len(1,2)=1$.
- $max\_deep$, represents the height of the entire tree. For example, when $n=2$, $max\_deep=2$. When $n=9$, $max\_deep=4$.
- $deep(node)$ calculates the depth of a specific node.
- $number\_of\_nodes\_at\_layer(layer)$ indicates how many nodes there are in a certain layer in this tree. For example, when $n=4$, $number\_of\_nodes\_at\_layer(2)=2$, $number\_of\_nodes\_at\_layer(3)=1$.
Overall Approach
The problem can be broken down into three main steps:
Step 1: Maintain a $dp\_s[i][j]$, representing all possibilities of a path of length $j$ where the maximum value $s$ is $i$. Here, $1\leq i\leq m$，$1\leq j \leq 2 \cdot max\_deep - 1$.
(In other words, the longest possible path in this tree contains at most $2 \cdot max\_deep - 1$ nodes)
Step 2: Maintain a $dp\_len[i]$, representing the total number of paths with length $i$ in this tree.
For instance, when $n=4$, $dp\_len[2]=3$, $dp\_len[1]=4$.
Step 3: Calculate the final result. The final result equals $\sum_{len=1}^{2 \cdot max\_deep - 1}dp\_len[len]\cdot m^{n-len} \cdot (\sum_{s=1}^{m} s\cdot dp\_s[s][len])$.
This means, for each specified length of the path $len$:
There are $dp\_len[i]$ different paths.
Nodes outside of this path can be chosen arbitrarily, leading to $m^{n-len}$ possibilities.
Nodes within this path, for each possible $s$, offer $dp\_s[s][len]$ choices. Finally, the result needs to be multiplied by $s$ in the calculation.
Why this idea?
Two key points:
- The expression $\sum_{i=1}^n\sum_{j=i}^n s_{i,j}$ involves summation, and the final result also requires a double summation over this. It is natural to consider rearranging $s_{i,j}$. Unify the summation.
- Since $dp\_s[i][j]$ is relatively easy to obtain, the only thing missed from the final result is $dp\_len[i]$. This problem seemed to resemble a classic one, and it was assumed there should be an existing solution.
Calculation of $dp\_s[i][j]$
Firstly, a straightforward combinatorial method came to mind. It's clear that $dp\_s[i][j]=\sum_{k=1}^{j} C_j^k\cdot (i-1)^{j-k}$.
In other words, select $k$ out of $j$ nodes and set their value to $i$, while the values of other nodes can be any value between $1$ and $i-1$.
However, this method has an issue with its time complexity: $O(m\cdot max\_deep^2)\approx 10^5 \cdot {(10^2)}^2 \approx 10^9$. This is because for each $i,j$, we need to loop through $k$.
So, I tried to observe the relationship between $dp\_s[i][j]$ and other nodes. I noticed that $dp\_s[i][j]=i\cdot dp\_s[i][j-1] + \sum_{k=1}^{i-1} dp\_s[k][j-1]$.
This means either the maximum value of the previous $j-1$ nodes was already $i$, allowing the new node to be any value between $1$ and $i$.
Or the previous maximum value was less than $i$, and the new node must be $i$.
The term $\sum_{k=1}^i dp\_s[k][j-1]$ can be maintained as a prefix sum, so the complexity is $O(m\cdot max\_deep)$.
Calculation of $dp\_len[i]$
There are various methods to solve this, and I chose a relatively straightforward approach.
For a given path, if we know its starting and ending points, we can determine the length of this path and all the nodes it passes through.
Furthermore, if we know the starting point, the topmost point, and the depth of the ending point of this path, we can calculate: 1. The length of this path; 2. The total number of such paths.
Let's denote the starting point as $from$, the depth of the topmost point as $father$, and the depth of the ending point as $to$. It's not hard to find that for each pair $[from, father, to]$, the length of this path is $[father-deep(from)] + (father - to) + 1$, and there are $2^{to - father -1}$ possible paths.
So, $dp\_len[father-deep(from) + (father - to) + 1]+=number\_of\_nodes\_at\_layer(deep(from))\cdot 2^{to - father -1}$. In other words, we iterate through $deep(from)$, for each starting point with depth $deep(from)$, we iterate through the depth of the topmost point and the depth of the ending point, and add the result to $dp\_len[i]$ one by one.
(Note that this idea chooses a fixed starting point, not the depth of the starting point.)
There are two issues here:
1. When $father=to$, there is only 1 possible path. We handle this as a special case.
2. When $deep(from)=to$, many paths are counted twice. This is more complicated to handle.
For the second issue, I chose to handle it separately.
So, first, in the calculation process mentioned above, when enumerating $to$, limit its range to $deep(from)-1$. This ensures that at least the starting and ending points have different depths, making our results correct. It also handles non-complete binary trees.
For the case where the depths of the starting and ending points are the same, we consider the situation of the topmost point of the path. Because two leaf nodes must be in the left and right subtrees of the topmost node.
So, For non-complete binary trees, there are three possible scenarios for these left and right subtrees: 1. Both subtrees are complete; 2. At least one of subtree is not complete; 3. At least one of subtrees don't reach the required depth.
Let's denote the depth of the starting and ending points as $target$ and the depth of the topmost point as $father$.
For the first scenario, for each $father$, there are $(2^{target-father -1})^2$ possible selections. There are $\lfloor\frac {number\_of\_nodes\_at\_layer(target)} {2^{target-father}}\rfloor$ fathers satisfying this condition.
For the third scenario, obviously, there are 0 possibilities.
For the second scenario, there is only one father that satisfies this condition. To calculate its selection count, we need to find out how many leaf nodes are in its right subtree. It can be observed that the right subtree has $\max([number\_of\_nodes\_at\_layer(target) \% (2^{target-father})] - (2^{target-father -1}),0)$ leaf nodes, denoted as $num\_right$ (subtracting left subtree and first scenario). So, its selection count is $num\_right \cdot (2^{target-father -1})$.
Finally, add up all the above results to $dp\_len[i]$. Which is $dp\_len[(target-father) * 2 + 1]+=(2^{target-father -1})^2\cdot \lfloor\frac {number\_of\_nodes\_at\_layer(target)} {2^{target-father}}\rfloor +$$(2^{target-father -1}) \cdot \max([number\_of\_nodes\_at\_layer(target) \% (2^{target-father})] - (2^{target-father -1}),0) $
代码
Java
C++
