题解

思路

传递闭包不改变顶点之间的可达关系。一个强连通分量内任意两点互相可达，因此闭包后可以按任意顺序经过分量内所有顶点。把强连通分量缩点后得到 DAG，一条简单路径等价于在这个 DAG 上选一条链，并完整取走链上每个分量。

做法

先求强连通分量。每个分量的长度贡献为点数，权值贡献为点权和。对缩点 DAG 做拓扑动态规划：状态保存到达该分量时可获得的最大总点数；长度相同时保留较小的总权值。

强连通子任务只有一个分量，答案就是 $n$ 与全部点权和。小规模可以显式求传递闭包，再用子集动态规划枚举简单路径。

独立复核实现使用迭代 Tarjan 求强连通分量，并从汇点反向计算最长链。

复杂度

每组时间复杂度 $O(n+m)$，空间复杂度 $O(n+m)$。