题解

思路

令 $dp_t(v)$ 表示从顶点 $1$ 出发恰走 $t$ 条边并停在 $v$ 的最大权值。直接沿每条无向边转移即可在 $O(m)$ 时间得到下一层。

考虑一条边 $e=(u,v,w)$。若某条路径在走了 $t$ 步后停在 $u$ 或 $v$，此后可以一直沿 $e$ 往返。因此对任意 $x\ge t$，可以得到权值

对每条边保留 $0\le t\le m$ 中最大的截距 $b_e$。任意长度大于 $m$ 的最优路径都可删除一个重复出现的边段，并把对应边往返补到目标长度，因此

前 $m$ 项直接动态规划；后面的项是至多 $m$ 条直线在连续整数横坐标上的最大值。按斜率排序、相同斜率只保留最大截距，再维护上凸壳及每条直线开始最优的第一个整数位置，即可按等差数列分段求和。

做法

子任务 1：枚举全部路径

深度优先搜索从顶点 $1$ 出发的所有长度不超过 $q$ 的路径，逐层记录最大权值。

子任务 2：逐长度动态规划

连续执行 $q$ 次边转移并累加每层最大值，复杂度为 $O(qm)$。

子任务 3：DP 与直线上凸壳

只执行前 $m$ 层 DP，同时更新每条边的最佳截距。对这些直线建立整数上凸壳，将 $[m+1,q]$ 分成若干段，对每段的 $wx+b$ 用等差数列公式求和。

正确性证明

引理 1

动态规划正确求出 $F_1,\ldots,F_m$。

证明。 每条长度为 $t+1$ 的路径由一条长度为 $t$ 的路径再经过一条相邻边得到；逐边取最大值恰好枚举全部末步。$\square$

引理 2

对 $x>m$，$F_x=\max_e(wx+b_e)$。

证明。 每条直线对应一条合法前缀及随后在边 $e$ 上往返，故右侧不超过真实最优值。反向取一条最优长路径；其前 $m+1$ 个顶点间经过 $m$ 条边种类以上时必有可抽取的重复边段。在无向图中可将被抽取部分替换为同一边往返而保持任意剩余长度。反复缩短到不超过 $m$ 的前缀，得到某条已记录直线，且权值不减。故真实最优值也不超过右侧。$\square$

引理 3

上凸壳分段给出每个整数 $x\in[m+1,q]$ 的最大直线值。

证明。 斜率递增时，两条直线的优劣只改变一次。删除永不最优的中间直线后，各保留直线的最优区间按斜率顺序连续排列，整数交点上取整即为新区间起点。$\square$

定理

算法输出 $\sum_{i=1}^{q}F_i$ 模 $10^9+7$。

证明。 引理 1覆盖前 $m$ 项；引理 2、3覆盖其余全部项。每段求和只是在模意义下重写相同的逐项和，故总结果正确。$\square$

复杂度

时间复杂度为 $O(m^2+m\log m)$，空间复杂度为 $O(n+m)$。