28011번 - LaLa and Harvesting 스페셜 저지다국어

Every other winter, $\color{blue}{\text{LaLa}}$ helps her aunt, $\color{red}{\text{Aisha}}$, harvest a crop native to the Biheiril Kingdom.

The crop can be modeled as a graph where an edge corresponds to a branch, a vertex to a joint, and a fruit with tastiness $T_u$ grows on each joint $u$.

The cultivation of the crop can be divided into three phases.

1. At the start of the first phase, a seed is planted on an open field. The seed eventually grows to form a cactus graph, a simple connected graph where every edge belongs to at most one cycle. This is the only phase where new joints grow.
2. Consider the DFS-tree of the cactus grown during the first phase. At the start of the second phase, $\color{red}{\text{Aisha}}$ encloses the crop with a ring-shaped framework by attaching the leaves (vertices of degree 1, where only the edges in the DFS-tree are counted for degree, which possibly includes the root of the DFS-tree) to the ring. This forces the crop to grow additional branches joining adjacent joints on the framework, forming a cycle graph, and to start producing the fruits. Please read the input specification for detailed description.
3. At the start of the third phase, $\color{red}{\text{Aisha}}$ connects to the framework a $\color{red}{\text{m}} \color{brown}{\text{a}} \color{orange}{\text{g}} \color{blue}{\text{i}} \color{magenta} {\text{c}}$ tool that feeds the crop with the constant flow of extra nutrition. As a result, some new branches grow. The union of the branches grown during this phase form a very dense tree: every non-leaf vertex of the tree has degree $\ge 12$. The harvesting begins at the end of this phase.

$\color{blue}{\text{LaLa}}$'s goal is to maximize the sum of tastiness of the fruits she has harvested. However, $\color{blue}{\text{LaLa}}$ is not allowed to harvest fruits at two adjacent vertices, as it will stress and kill all the trunks directly connecting them.

Write a program that computes a set of fruits $\color{blue}{\text{LaLa}}$ can harvest which has maximum possible sum of tastiness.

The input describes the state of a crop and is given in the following format:

$N$ $M$

$T_0$ $T_1$ $\cdots$ $T_{N-1}$

$u_0$ $v_0$

$u_1$ $v_1$

$\vdots$

$u_{M-1}$ $v_{M-1}$

$K$

$x_0$ $y_0$

$x_1$ $y_1$

$\vdots$

$x_{K-1}$ $y_{K-1}$

where $N$ is the number of joints, numbered from $0$ to $N-1$, $M$ the number of branches grown during the first phase, and the $i$-th branch connects the joints $u_i$ and $v_i$ for all integers $0 \le i < M$.

Consider the DFS-tree built over the cactus graph grown during the first phase where the DFS traversal starts at joint $0$ and the order of the neighbors of each joints is given by the input order i.e. the traversal prioritizes branches given sooner in the input. Note that the above description uniquely defines a DFS-traversal and its corresponding DFS-tree. Let $c_0, \cdots, c_{l-1}$ be the subsequence of the DFS-order consisting of all joints which has degree $1$ in the DFS-tree. Then the cycle graph grown during the second phase is defined by the $l$ edges $(c_0, c_1), \cdots, (c_{l-1}, c_0)$.

In addition, $K$ is the number of branches grown on the third phase, $i$-th of which connects the joints $x_i$ and $y_i$ for all integers $0 \le i < K$.

The input satisfies the following constraints:

• All the numbers in the input are integers.
• $2 \le N \le 500$, $N-1 \le M \le 2N$, $1 \le K \le \min(N-1, 100)$
• $1 \le T_u \le 200\,000$ for all integers $0 \le u < N$
• $0 \le u_i < v_i < N$ for all integers $0 \le i < M$
• $u_i \ne u_j$ or $v_i \ne v_j$ for all integers $0 \le i < j < M$
• $0 \le x_i < y_i < N$ for all integers $0 \le i < K$
• $x_i \ne x_j$ or $y_i \ne y_j$ for all integers $0 \le i < j < K$
• The union of edges $(u_i, v_i)$ forms a cactus over the vertices $\lbrace {0, 1, \cdots, N-1} \rbrace$.
• The union of edges $(x_i, y_i)$ forms a tree over the set of vertices $\lbrace x_0, y_0, x_1, y_1, \cdots, x_{K-1}, y_{K-1} \rbrace$ where each vertex with degree greater than $1$ has degree at least $12$.

The output should be in the following format:

$W$ $L$

$s_0$ $s_1$ $\cdots$ $s_{L-1}$

where $W$ is the maximum sum of tastiness of a set $s = \lbrace s_0, \cdots, s_{L-1} \rbrace$ of fruits $\color{blue}{\text{LaLa}}$ can harvest from the crop without harming any branches.

The output should satisfy the following constraints:

• All the numbers in the output are integers.
• $0 \le L \le N$
• $0 \le s_0 < s_1 < \cdots < s_{L-1} < N$
• There are no edges directly connecting the vertices $s_i$ and $s_j$ for all integers $0 \le i < j < L$.
• $\sum_{i=0}^{L-1}T_{s_i} = W$

The following illustrates the crop described in the sample test.

• The regular black edges denote the branches grown during the first phase that is part of the DFS-tree.
• The dotted black edges denote the branches grown during the first phase that is NOT part of the DFS-tree.
• The red edges denote the branches grown during the second phase.
• The blue edges denote the branches grown during the third phase.

Note that there can be multiple branches directly connecting the same pair of joints.