题目分析
本题要求在给定的 DAG 上进行一个多轮路径选择游戏，每轮选择的路径长度必须满足模数条件，目标是最大化一个与路径长度和轮次相关的分数。

---

算法思路

核心思想：动态规划 + 拓扑排序

关键观察：

• 游戏最多进行 $n-1$ 轮（因为只有 $n$ 个节点）
• 第 $i$ 轮要求路径边权和是 $i+1$ 的倍数
• 分数公式：$\frac{\sum_{i=1}^k a_i |p_i|}{k}$

---

算法流程详解

1. 状态设计

int dp[103][103][103];

• dp[i][j][k]：进行到第 $i$ 轮，当前在节点 $j$，路径总长度模 $i$ 余 $k$ 时的最大 $\sum a_t|p_t|$
• 第一维：轮次（2 到 $n$）
• 第二维：当前节点
• 第三维：路径长度模当前轮次的余数

2. 初始化

dp[1][F][0] = 0;  // 第1轮从起点F开始，余数为0

3. 拓扑排序处理节点

for (int i = 1; i <= N; ++i)
    if (!deg[i]) q.push(i);
while (!q.empty()) {
    int t = q.front(); q.pop();
    top[++ctop] = t;
    for (auto p : ch[t])
        if (!--deg[p.first]) q.push(p.first);
}

确保 DP 转移时按照拓扑序进行，避免后效性。

4. 动态规划转移

情况1：开始新路径

for (int j = 1; j <= N; ++j)
    if (dp[i-1][j][0] >= 0)  // 上一轮在j结束且余数为0
        for (auto p : ch[j])
            chkmax(dp[i][p.first][p.second % i], 
                   dp[i-1][j][0] + A[i]);

从上一轮的结束节点开始一条新路径，第一条边的权重直接模 $i$。

情况2：延长当前路径

for (int j = 1; j <= N; ++j) {
    int x = top[j];  // 按拓扑序处理
    for (int k = 0; k < i; ++k)
        if (dp[i][x][k] >= 0)
            for (auto t : ch[x])
                chkmax(dp[i][t.first][(k + t.second) % i], 
                       dp[i][x][k] + A[i]);
}

在当前轮次内继续延长路径，累加边权并取模。

5. 分数计算与更新

int mx = dp[0][0][0];
for (int j = 1; j <= N; ++j)
    if (dp[i][j][0] >= 0)  // 当前轮次结束且余数为0
        chkmax(mx, dp[i][j][0]);

if (mx >= 0)
    ans = max(ans, ((fac){mx, i-1}));

每轮结束后，如果存在合法路径（余数为0），计算分数 $\frac{mx}{i-1}$ 并更新最优解。

---

关键技术与优化

1. 拓扑排序保证正确性

• DAG 的特性确保可以拓扑排序
• 按拓扑序转移避免循环依赖

2. 模数处理

• 每轮模数不同（等于轮次数）
• 通过模运算检查路径长度条件

3. 分数比较

struct fac { int p, q; };
bool operator <(fac p, fac q) {
    return p.p * q.q < p.q * q.p;
}

避免浮点数，使用交叉相乘比较分数。

4. 状态剪枝

只保留余数有意义的状态，减少空间开销。

---

复杂度分析

• 状态数：$O(n^3)$，$n \leq 100$
• 转移次数：$O(n^2 \times m)$
• 总复杂度：$O(n^3 + n^2m)$，完全可行

---

样例验证

样例1

输入：
5 5 1
1 11 21 1211
1 2 4
1 3 11  
2 5 9
3 4 12
4 5 13
输出：
6 1

• 第1轮：路径 1→2，长度4模2余0，得分 $1 \times 1 = 1$
• 第2轮：路径 2→5，长度9模3余0，得分 $11 \times 1 = 11$
• 总分：$(1+11)/2 = 6$

样例2

通过类似分析可得输出 221 3

---

算法优势

1. 完备性：考虑所有可能的轮次和路径组合
2. 正确性：拓扑排序保证转移顺序正确
3. 高效性：状态设计合理，复杂度可接受
4. 精度安全：分数运算避免浮点误差

该算法通过巧妙的状态设计和拓扑处理，完整解决了 DAG 上的倍增路径选择问题。