P4410 [HNOI2009] No-Return Island

Neverland is a magical place made up of several islands arranged in a ring. Each island is home to a distinct species, and creatures live on these islands. All these species share a common social habit: for any two creatures on the same island, they have exactly one common friend. That is, for any two creatures $a$ and $b$ on the same island, there exists exactly one creature $c$ who is a friend of both $a$ and $b$. Of course, some islands may have only one creature living alone. There is also communication between islands. Specifically, each island chooses the smartest creature as its representative, and this representative becomes friends with the representatives of its two neighboring islands. Unfortunately, World A plans to invade Neverland. As its guardian, Lostmonkey wants to know Neverland’s fighting power in a relatively unfavorable situation. Fighting alongside friends increases ability, so Lostmonkey wants to know the maximum fighting power without selecting any pair of friends. In other words, select some creatures such that no two selected creatures are friends, and maximize the sum of their battle power.

The first line contains two integers $n$ and $m$ separated by a space, denoting the number of creatures in Neverland and the number of friend pairs. Each of the next $m$ lines describes a friend pair. Specifically, each line contains two integers $a$ and $b$ separated by a space, indicating that creature $a$ and creature $b$ are friends (each friend pair appears exactly once). The $(m+2)$-th line contains $n$ integers separated by spaces, where the $i$-th integer denotes the battle power $A_i$ of creature $i$.

Output a single integer, the maximum total battle power satisfying the condition.

Sample explanation: There are four islands. Creature $1$ is on island $1$, creature $2$ is on island $2$, creatures $3$, $5$, $6$ are on island $3$, and creature $4$ is on island $4$. Constraints: $4 \le n \le 100000$, $1 \le a, b \le n$, $1 \le m \le 200000$, $-1000 \le A_i \le 1000$. Translated by ChatGPT 5