『MdOI R2』Odyssey

超越音速的极限，不及瑰丽多变的极光； 微弱的脉冲，开拓原本一片混沌的天地； 沉郁的蓝缓缓闪动，史诗的红迎接巅峰； 血色的夕阳尽头，是将夜的星辰； 夜半的满天星空，也会被来自地狱的硝烟掩盖； 炽红炼狱消逝，只金色遗迹永存。 在这里等待着每一位的，都是一段艰苦而璀璨的旅程。

若正整数 $a$ 与 $b$ 满足： - $a$ 与 $b$ 的积是一个正整数的 $k$ 次方，即存在正整数 $c$ 使得 $ab=c^k$。 那么我们称 $(a,b)$ 为一组**完美数对**。 --- 有一个包含 $n$ 个结点和 $m$ 条边的**有向无环图**，这张图中的每条边都有权值和长度两个属性。 如果一条路径 $P$ 满足**以下条件之一**，则称其为一条**完美路径**： - $P$ 中仅包含一条边。 - $P$ 从其起点开始依次为 $e_1, e_2, e_3, \ldots e_p$ 这 $p\ (p\ge 2)$ 条边，对于任意的 $1\leq i\leq p-1$，$e_i$ 的权值和 $e_{i+1}$ 的权值组成完美数对。 你需要求出图中最长完美路径的长度，一条路径的长度定义为这条路径上所有边的长度之和。

第一行：三个整数 $n,m,k$，分别表示有向无环图的结点数、边数和完美数对的参数。 接下来 $m$ 行：每行四个整数 $u,v,w,l$，表示有一条权值为 $w$，长度为 $l$ 的有向边从 $u$ 连向 $v$。

第一行：一个整数 $ans$，表示最长完美路径的长度。

5 7 2
2 5 2 5
5 3 18 9
2 4 6 7
4 3 6 3
2 1 24 2
1 4 6 8
1 5 8 4

14

【帮助与提示】 为方便选手测试代码，本题额外提供两组附加样例供选手使用。 [样例输入1](https://www.luogu.com.cn/paste/wx1lz6m2) [样例输出1](https://www.luogu.com.cn/paste/28xe7f0x) [样例输入2](https://www.luogu.com.cn/paste/efgwngs5) [样例输出2](https://www.luogu.com.cn/paste/5hcpoayt) ---- 【样例解释】 样例中给出的有向无环图如图所示，其中边上的红色数字为边的权值，黑色数字为边的长度：  最长完美路径为 $2\to 5\to 3$，因为这两条边的权值 $2$ 和 $18$ 满足 $2\times 18=6^2$，是完美数对，此路径长度为 $5+9=14$。 此外，$2\to 1\to 4\to 3,\ \ 2\to 4\to 3,\ \ 1\to 5\to 3$ 等也是完美路径，但不是最长的。 图中，$2\to 1\to 5\to 3$ 长度为 $15$，是一条更长的路径，但它并不是完美路径，因为前两个边权 $24$ 和 $8$ 的乘积为 $192$，不是正整数的平方，即 $(24,8)$ 不是完美数对。 --- 【数据范围】 **本题采用捆绑测试。** 对于 $100\%$ 的数据：$1\leq n\leq 10^5,\ \ 1\leq m\leq 2\times 10^5,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^5,\ \ 1\leq l\leq 10^4$。 给出的图**不保证弱连通**，图中从一个点到另一个点**可能**存在多条边，但保证给出的图是有向无环图。 | 子任务编号 | $n\leq$ | $m\leq$ | $w\leq$ | $k\leq$ | 特殊性质 | 分值 | | :--------: | :-----: | :--------------: | :-----: | :-----: | :--------: | :--: | | Subtask 1 | $10^5$ | $2\times 10^5$ | $10^5$ | $1$ | 无 | $18$ | | Subtask 2 | $10$ | $10$ | $100$ | $2$ | 无 | $12$ | | Subtask 3 | $600$ | $1.5\times 10^3$ | $10^3$ | $2$ | 无 | $10$ | | Subtask 4 | $10^5$ | $2\times 10^5$ | $10^5$ | $2$ | $w$ 为素数 | $15$ | | Subtask 5 | $10^5$ | $2\times 10^5$ | $10^5$ | $2$ | 无 | $15$ | | Subtask 6 | $600$ | $1.5\times 10^3$ | $10^3$ | $5$ | 无 | $10$ | | Subtask 7 | $10^5$ | $2\times 10^5$ | $10^5$ | $10$ | 无 | $20$ |