P7146 [THUPC 2021 初赛] 独立

feecle6418 备注：可以认为本题的数据是随机生成的。

给定一张 $n$ 个点 $m$ 条边的无向图。 对于 $\{1, 2, \ldots , n\}$ 的某个子集 $A$，$A$ 的分数为： 1. 初始分数为 $0$； 2. 对于所有 $i \in A$，分数加 $a_i$； 3. 对于所有边 $(u, v, k)$（代表从 $u$ 到 $v$ 值为 $k$ 的边）满足 $u \in A$ 并且 $v \in A$，分数减 $k$； 现在请你计算出所有的 $A$ 中，分数最高是多少。

令 $q = 101$，$b = 137$，$p = 1, 000, 000, 007$。 第一行包含六个整数 $n, m, x_0, y_0, a_0, z_0$（$1 \le n \le 100000$，$0 \le m \le \frac n2$，$0 \le x_0, y_0, a_0, z_0 < P$）。 对于 $1 \le i \le n$，有 $a_i = (q \times a_{i - 1} + b) \bmod p$。 对于 $1 \le i \le m$, 有 $x_i = (q \times x_{i − 1} + b) \bmod p$，$y_i = (q \times y_{i − 1} + b) \bmod p$，$z_i = (q \times z_{i − 1} + b) \bmod p$。对于每一组 $(x_i, y_i, z_i)$ 描述了一条连接 $(x_i \bmod n) + 1, (y_i \bmod n) + 1$ 的值为 $z_i$ 的边，如果 $x_i = y_i$ 或者之前出现过连接 $x_i$ 和 $y_i$ 的边，则忽视这条边（即这条边不存在）。

输出一行一个整数表示最高分数。

**【题目来源】** 来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。 题解等资源可在 查看。