Background

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

Problem Description

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.

Input Format

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 Format

Output one line with one integer, the maximum score.

10 5 1 2 3 4

3909327860

Hint

[Source]

From the 2021 Tsinghua University Student Programming Contest and Collegiate Invitational (THUPC2021) Preliminary Round.

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2021-pre.

Translated by ChatGPT 5