核心思路

1. 状态设计

由于边权只有 $1, 2, 3$，我们可以将每个节点拆成 3 个状态：

• $v_1$: 到达 $v$ 且最后一步走的是长度为 $1$ 的边
• $v_2$: 到达 $v$ 且最后一步走的是长度为 $2$ 的边
• $v_3$: 到达 $v$ 且最后一步走的是长度为 $3$ 的边

实际上代码中用的是：

• $3v-2$: 表示还需要走 1 步才能完成一条完整路径
• $3v-1$: 表示还需要走 2 步才能完成一条完整路径
• $3v$: 表示还需要走 3 步才能完成一条完整路径

2. 转移矩阵构建

状态转移规则：

• 从 $3u-2$ 到 $3v-2$: 需要边权 $1$ 的边 $u→v$
• 从 $3u-1$ 到 $3v-2$: 需要边权 $2$ 的边 $u→v$
• 从 $3u$ 到 $3v-2$: 需要边权 $3$ 的边 $u→v$

内部转移（延迟计数）：

3v-2 → 3v-1 → 3v

这样就把长边拆成了多个长度为 1 的"步骤"。

3. 路径计数公式

设 $f_L[v]$ 表示长度为 $L$ 的到达 $v$ 的路径数。

转移：

$$f_L[v] = \sum_{u→v \text{ with weight } w} f_{L-w}[u] $$

由于 $w \in \{1,2,3\}$，这是三阶线性递推，可以用矩阵快速幂。

4. 累计路径数

我们要求的是长度 $\le ans$ 的路径总数是否 $\ge k$。

在矩阵中加入一个累计节点 $s$：

• 从每个完整路径状态 $3v-2$ 连到 $s$（计数一次）
• $s$ 自环保持累计和

这样矩阵的 $[start][s]$ 就是长度 $\le$ 当前幂次的路径总数。

5. 二分答案

使用倍增（二进制拆分）来二分：

• 从高位到低位尝试
• 用矩阵快速幂检查路径数
• 如果 $count < k$，就加上这一位

6. 边界处理

• 初始状态：每个节点作为起点，$w.a[3v-2][3v-2] = 1$
• 最终答案要减去 $n$（去掉长度为 0 的路径）
• 用 __int128 和 min(..., L) 防止溢出

时间复杂度

• 矩阵大小 $O(n)$
• 矩阵乘法 $O(n^3)$
• 二分 $O(\log k)$ 次
• 总复杂度 $O(n^3 \log k)$，对于 $n \le 40$ 可接受

这种状态拆分+矩阵快速幂+二分的方法巧妙处理了边权多样性和超大 $k$ 的问题。