P14833 [THUPC 2026 初赛] 生命线

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛。 题解等资源可在 查看。

对于一个长为 $n$ 的、仅由 $a,b,\ldots ,z$ 构成的字符串 $s$，考虑一张含 $n$ 个点的无向带权图，每两个点 $i,j (i \neq j)$ 间有权值为 $\operatorname{LCP}(suf_i,suf_j)^\dagger$ 的边，其中 $suf_i = s[i:n]$。 Ecrade_ 定义字符串 $s$ 的价值为该图最大生成树的边权之和。 Ecrade_ 想要请你找出所有长为 $n$ 的、仅由 $a,b,\ldots ,z$ 构成的字符串中，价值第 $k$ 小的任意一个。 $^\dagger$ $\operatorname{LCP}(s_1,s_2)$ 定义为字符串 $s_1$ 与 $s_2$ 的最长公共前缀的长度。

从标准输入读入数据。 第一行一个整数 $T (1 \leq T \leq 2 \times 10^5)$，表示测试数据组数。 对于每组测试数据，一行两个整数 $n,k (1 \leq n, \sum n \leq 4 \times 10^5, 1 \leq k \leq \min(26^n, 10^{15}))$。

输出到标准输出。 对于每组测试数据，第一行输出第 $k$ 小的价值，第二行输出一行一个长为 $n$ 的、价值第 $k$ 小的字符串。若有多个字符串满足条件，输出其中任意一个即可。

### 【样例 1 解释】 ·对于第一组测试数据，长为 $2$ 的字符串中，第 $1$ 小（即最小）的价值为 $0$，一个满足条件的字符串为 ``hi``。当然，``ab``、``yz`` 等字符串也满足条件。 ·对于第二组测试数据，长为 $2$ 的字符串中，第 $676$ 小（即最大）的价值为 $1$，一个满足条件的字符串为 ``gg``。当然，``aa``、``zz`` 等字符串也满足条件。 ·对于第三组测试数据，长为 $3$ 的字符串中，第 $16000$ 小的价值为 $1$ ，一个满足条件的字符串为 ``qwq``。当然，``cpp``、``lol`` 等字符串也满足条件。