解题思路
设某个节点 u 的缓存中有若干条完整 token 序列，请求序列为 r，则该节点与请求的匹配长度为：
LCP(u,r)=s∈cacheumaxcommonPrefixLen(s,r)
每次请求到来时，需要选择：
P4970.第3题-KV Cache 感知的推理请求路由
题目内容
实现一个多节点 LLM 推理集群的请求路由器。每个节点维护一个 KV Cache，缓存已处理请求的完整 token 序列（模拟 prefill 完成后 KV 被缓存）。新请求到来时，选择能复用最多 KV Cache 的节点以减少 prefill 计算量；命中长度相同时，选负载最轻的节点。
背景：在实际 LLM 推理系统中（如 vLLM、SGLang），若新请求的前缀与某节点已缓存的请求存在公共前缀，该部分的 prefill 计算可直接复用，显著降低 TTFT（Time To First Token）。
路由规则（按优先级）：
选与当前请求拥有最长公共前缀（LCP）的节点
若多个节点 LCP 长度相同（含均为 0），选当前队列中待处理 token 总量最少的节点
状态更新（每条请求路由后立即执行，模拟 prefill 完成）：
将请求的完整 token 序列加入所选节点的缓存
将请求的 token 数（len(request)）累加到所选节点的负载上
解答要求
时间限制：C/C++ 1000ms，其他语言：2000ms
内存限制：C/C++ 512MB，其他语言：1024MB
输入描述
Line 1: N M # N个节点，M个请求
Line 2: load[0..N−1] # 每个节点初始待处理 token 数
Line 3~N+2: K seq0 seq1 ... # 每个节点初始缓存：K条序列，各序列 token 逗号分隔。K=0 时该行只有 “0”
Line N+3~end: t0 t1 t2 ... # 每条请求的 token 序列，空格分隔，共 M 行
输出描述
一行，M 个整数，assignment[i] 为第 i 条请求分配的节点编号（0-indexed）。
样例1
输入：
3 4
100 50 200
0
0
0
10 20 30 40 50
10 20 30 40 60
10 20 30 40 50 70
5 6 7 8
输出：
1 1 1 1
解释：逐步分析：
| 请求 |
最长LCP |
路由 |
原因 |
| 10,20,30,40,50 |
0（无缓存） |
节点1 |
负载最轻（50） |
| 10,20,30,40,60 |
节点1:4 |
LCP 最长 |
| 10,20,30,40,50,70 |
节点1:5（命中第1条） |
| 5,6,7,8 |
0（无命中） |
负载最轻（50+5+5+6=66，节点0=100，节点2=200） |
样例2
输入：
2 4
0 0
1 1,2,3,4,5
0
1 2 3 4 5 6 7
8 9 10 11
1 2 3 4 5 100 200
99 88 77
输出：
0 1 0 1
解释：逐步分析：
| 请求 |
最长LCP |
路由 |
原因 |
| 1,2,3,4,5,6,7 |
节点0（命中缓存 1,2,3,4,5） |
节点0 |
LCP 更长 |
| 8,9,10,11 |
0 |
节点1 |
LCP 相同，节点1负载(0) < 节点0(7) |
| 1,2,3,4,5,100,200 |
5 |
节点0 |
LCP 更长 |
| 99,88,77 |
0 |
节点1 |
LCP 相同，节点1负载(4) < 节点0(14) |
