考虑将答案转化为期望，最后乘上 $2^{n-1}$。

如果 $a_i$ 前是加号，有 $\frac{1}{2}$ 的概率，因此贡献为 $\frac{a_i}{2}$。

如果 $a_i$ 前是乘号，有 $\frac{1}{2}$ 的概率，贡献是 $\frac{a_i-1}{2}$ 乘以前 $i-1$ 个数的期望后缀乘积，这个可以递推算出来。

时间复杂度：$\mathcal O(n)$。

简要题解：

先手推一波式子：

$$f(i,m)=a^{m-1}\times f(i,1)+\frac{a^{m-1}-1}{a-1}\times b$$

再次展开，得：

$$\begin{bmatrix}f(i,m) & 1\end{bmatrix}\times \begin{bmatrix}a^{m-1}\times c & 0\\a^{m-1}\times d+\frac{a^{m-1}-1}{a-1}\times b & 1\\\end{bmatrix}=\begin{bmatrix}f(i+1,m) & 1\end{bmatrix}$$

高精度十进制快速幂即可。

注意特殊处理 $a=1$ 的情况。

显然的贪心思路：让被经过期望次数多的边的编号尽量小。但是这题 $m$ 可能为 $10^5$ 级别，不能对边进行求解。

考虑求出每个点的期望经过次数，设其为 $f_i$，令点 $i$ 的度数为 $deg_i$。

则有:

$$f_1=(\sum\limits_{(1,v)\in E\land v\neq n} \frac{f_v}{deg_v})+1,f_i=\sum\limits_{(i,v)\in E\land v\neq n}\frac{f_v}{deg_v}(1\lt i\lt n)$$

$v\neq n$ 的原因是，一旦 $v=n$，就走到 $n$ 了，肯定不可能再走回 $i$。

因为有后效性，所以将其列成矩阵进行高斯消元求解。

则：

$$\forall (u,v)\in E,g(u,v)=\frac{f_u}{deg_u}+\frac{f_v}{deg_v}$$

其中 $g(u,v)$ 表示边 $(u,v)$ 被经过的期望次数。

注意特判 $u\neq n,v\neq n$，原因同上。

时间复杂度 $\mathcal O(n^3)$。

upd：修改一处笔误。

神仙 Kubic 的思路真的简洁而自然，我这种小蒟蒻也能看明白 qwq。

（Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？）

先将 $s,t$ 升序排序，定义 $a_i$ 表示最小的能和第 $i$ 头牛匹配的牛棚，$b_i$ 表示最小的能和第 $i$ 个牛棚匹配的牛。

假设最小的未被匹配的牛为 $p$，则「极大匹配」的充要条件为 $s_p\gt t_{a_p}$。

考虑枚举这个最小未被匹配的牛，设其编号为 $i$。

不难发现，$[a_i,n]$ 范围内的牛棚必须被匹配，否则 $i$ 一定可以和 $a_i$ 匹配。

$1\sim i-1$ 的牛必然能和 $[a_i,n]$ 内的牛棚匹配，$i+1\sim n$ 的牛则不一定。

考虑枚举 $1\sim i-1$ 匹配到 $[a_i,n]$ 内的牛棚的数量为 $j$，那么就需要 $1\sim i-1$ 未被匹配的牛全部与 $[1,a_i)$ 内的某个牛棚匹配（根据条件），$i+1\sim n$ 的某些牛和 $[a_i,n]$ 内未被匹配的 $n-a_i+1-j$ 个牛棚匹配。

这个问题并不难解决。设 $f_{i,j}$ 表示前 $i$ 个牛棚和 $j$ 头牛匹配的方案数，$g_{i,j}$ 表示后 $i$ 头牛和 $j$ 个牛棚匹配的方案数。

转移方程：$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times \max\{0,b_i-j+1\},g_{i,j}=g_{i+1,j}+g_{i+1,j-1}\times \max\{n-a_i-j+2,0\}$。

则上述方案总数可以表示为 $g_{i+1,n-a_i+1-j}\times f_{a_i-1,i-j-1}\times j!$。

最后不要忘了加上 $f_{n,n}$，表示「完美匹配」的方案数。

不会写的做法，不保证正确：

首先发现前缀后缀是否相等可以直接哈希判断，那么这个问题就化为了求 $s_{i+1\sim n-i}$ 的 border。

我并没有发现这个东西可以类 KMP 势能分析均摊 $\mathcal O(1)$ 计算的性质，但是我学过一点点后缀数组，知道 LCP（最长公共前缀）的一个性质：

$$\forall 1\le i\lt j\lt k\le n,\text{LCP}(sa_i,sa_k)=\min\{\text{LCP}(sa_i,sa_j),\text{LCP}(sa_j,sa_k)\}$$

把 $\gt \lceil \frac{n}{2} \rceil$ 的 $sa$ 值标记一下，从前往后递推一遍，得到每个 $sa_i$ 前面第一个被标记过的 $sa$，用 RMQ 求值即可。

时间复杂度 $\mathcal O(n\log n)$，后缀数组常数卡小点估计能过，但一点也不精妙。

定义 $f_i$ 表示 $s_{i+1\sim n-i}$ 的最长不重叠公共前后缀长度。

当我们从大到小枚举 $i$，显然有 $f_i\le f_{i+1}+2$。

从洛谷题解搬的一张图：

那么我们不妨令 $f_i=f_{i+1}+2$，用哈希判合法性，不合法时暴力往前跳。

和 KMP 类似，势能总和为 $n$，那么总的时间复杂度就是 $\mathcal O(n)$。

很有启发的一道题，从中认识到，不能忽视原题中某些「显而易见」的性质，认真分析，它们有可能就是通往正解的钥匙。

更好的阅读体验

补充：这个解法是我自己的，相当麻烦，有比我简洁的 DP 做法，还有 dottle 老师的神奇最短路做法，推荐去洛谷题解看看。

首先，看到 $k\le 3$ 的范围，显然是要分类讨论。

k=1

显然，最小花费即为 $u\to v$ 在树上路径的点权和。倍增预处理，每次查询 LCA 然后树上前缀和即可。

时间复杂度 $\mathcal O((n+m)\log n)$。

k=2

先考虑暴力的做法。将 $u\to v$ 在树上的路径拆下来，将点权写作序列 $b_{1\sim p}$ 研究。

我们用动态规划解决这个问题。设 $f(i)$ 表示 $1\sim i$ 的最小花费。

初始状态：$f(1)=b_1$。

状态转移方程：$f(i)=\min\{f(i-1)+b_i,f(i-2)+b_i\}$。

如果对矩阵很熟悉，不难发现这个就是一个矩阵优化的板子。

不过此处 $b_i$ 是变量，无法进行矩阵快速幂，当时考场上想到这里我脑子莫名其妙宕机了，感觉这题正解绝对是矩阵，但这个东西不会处理啊，然后就彻底蒙了，完全想偏了，最后打了暴力。

实际上和快速幂没有任何关系。因为是树上的静态查询问题，自然可以往倍增想。

因为矩阵满足交换律和结合律，完全可以把矩阵先存起来预处理，最后查询的时候再一次倍增求解。

先把上面那个式子写成矩阵：

$$\begin{bmatrix}f(i-1) & f(i-2)\end{bmatrix}\times\begin{bmatrix}a_i & 0\\a_i & +\infty\end{bmatrix}=\begin{bmatrix}f(i) & f(i-1)\end{bmatrix}$$

为了方便，我们定义 $t=\text{LCA}(u,v)$，$k=3$ 时亦然。

把中间的转移矩阵存起来倍增预处理一下，询问的时候，因为正着走和倒着走没有区别，我们把 $u\to t\to v$ 拆成 $u\to t,v\to t$ 两条链，以 $u\to t$ 为例：

初始向量矩阵：

$$\begin{bmatrix}a_u & +\infty \end{bmatrix}$$

然后把 $fa_u\to t$ 上的转移矩阵全乘起来，就得到了 $u\to t$ 这条链上的答案。

类似地处理 $v\to t$，接下来考虑合并答案。

因为 $k=2$，只有两种可能：$u$ 走到 $t$ 再走到 $v$，或者不经过 $t$，直接从 $t$ 在 $u\to v$ 路径上的两个子节点处穿过。

记 $u\to t$ 的矩阵为 $P$，$v\to t$ 的矩阵为 $Q$，因为可以写作一维向量的形式，为了方便，我们直接将 $P$ 中的元素用类似序列下标的形式表示，即 $P(0),P(1)$。下面 $k=3$ 的情况里我们仍采用这种称呼。

针对两种情况，答案分别为 $P(0)+Q(0)-a_t,P(1)+Q(1)$，两者取 $\text{min}$ 即可。

时空复杂度 $\mathcal O(2^3\times (n+m)\log n)$。

k=3

其实 $k=3$ 大体思路和 $k=2$ 完全一致，只不过有一个小细节：答案路径上的节点不一定都是 $u\to v$ 这条链上的。

原因很简单，比如链上的点权都是 $10^9$ 级别，而与链相连的节点中有一个点权是 1，那走这个点显然更优。

题解里大部分做法是将距离设入状态中，我当时并没有想到，而是直接把链接出去的点再设计一个方程。

还是先考虑一条链上的暴力，因为与 $u$ 相连的点中，只有点权最小的有效，设这个最小点权为 $c_u$。

在 $k=2$ 的情况上再加一条：设 $g(i)$ 表示走到 $i$ 连接的点上的最小路径花费。

状态转移方程：

$$f(i)=\min\{f(i-1)+a_i,f(i-2)+a_i,f(i-3)+a_i,g(i-1)+a_i,g(i-2)+a_i\}\\g(i)=\min\{f(i-1)+c_i,f(i-2)+c_i,g(i-1)+c_i\}$$

考虑将这个东西写成矩阵，那么样子就长这样：

$$\begin{bmatrix}f(i-1) & f(i-2) & f(i-3) & g(i-1) & g(i-2)\end{bmatrix}\times \begin{bmatrix}a_i & 0 & +\infty & b_i & +\infty\\a_i & +\infty & 0 & b_i & +\infty\\a_i & +\infty & +\infty & +\infty & +\infty\\a_i & +\infty & +\infty & b_i & 0\\a_i & +\infty & +\infty & +\infty & +\infty\end{bmatrix}\\=\begin{bmatrix}f(i) & f(i-1) & f(i - 2) & g(i) & g(i-1)\end{bmatrix}$$

倍增预处理和查询就很类似了，略过。

最后的合并情况很多，这里我直接把所有情况对应的式子列出来，因为用文字真的很难写出来 QAQ，理解一下叭 awa，有兴趣可以自己推一下，如果实在嫌我的方法麻烦还是看别的大佬的题解吧 qwq：

$P(0)+Q(0)-a_t$

$P(3)+ Q(3)-c_t$

$P(1)+Q(1)$

$P(1)+Q(2)$

$P(1)+Q(4)$

$P(4)+Q(1)$

$P(2)+Q(1)$

所有情况取 $\text{min}$ 即可。时间复杂度 $\mathcal O(5^3\times (n+m)\log n)$。