P7146 [THUPC 2021 Preliminary] Independent

feecle6418 note: You may assume the testdata of this problem is generated randomly.

You are given an undirected graph with $n$ vertices and $m$ edges. For a subset $A$ of $\{1, 2, \ldots , n\}$, the score of $A$ is defined as follows: 1. The initial score is $0$. 2. For all $i \in A$, add $a_i$ to the score. 3. For every edge $(u, v, k)$ (meaning an edge between $u$ and $v$ with value $k$) such that $u \in A$ and $v \in A$, subtract $k$ from the score. Now, among all subsets $A$, compute the maximum possible score.

Let $q = 101$, $b = 137$, $p = 1, 000, 000, 007$. The first line contains six integers $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$). For $1 \le i \le n$, $a_i = (q \times a_{i - 1} + b) \bmod p$. For $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$. Each triple $(x_i, y_i, z_i)$ describes an edge connecting $(x_i \bmod n) + 1$ and $(y_i \bmod n) + 1$ with value $z_i$. If $x_i = y_i$ or an edge connecting $x_i$ and $y_i$ has appeared before, ignore this edge (i.e., this edge does not exist).

Output one line with one integer, the maximum score.

**[Source]** From the 2021 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2021) Preliminary Round. Resources such as editorials can be found at . Translated by ChatGPT 5