P5024 [NOIP 2018 Senior] Defend the Kingdom

NOIP 2018 Senior D2T3.

Country Z has $n$ cities and $(n - 1)$ two-way roads. Each road connects two cities, and any two cities can reach each other through some roads. The Minister of Defense, Little Z, wants to station armies in the cities. The deployment must satisfy the following conditions: - A city may have an army stationed, or may have no army stationed. - For any two cities directly connected by a road, at least one of them must have an army stationed. - Stationing an army in a city costs money. The cost of stationing an army in city $i$ is $p_i$. Little Z quickly finds a deployment plan with the minimum total cost. However, the king then提出 (tíchū) $m$ requirements. Each requirement specifies whether two particular cities must have armies stationed or must not have armies stationed. Little Z needs to answer each requirement one by one. Specifically, if the king’s $j$-th requirement can be satisfied together with the deployment conditions above (without considering any other requirements beyond the $j$-th one), output the minimum total cost under this requirement. If the $j$-th requirement cannot be satisfied, output $-1$. Please help Little Z.

The first line contains two integers and a string, in order: the number of cities $n$, the number of requirements $m$, and the data type $type$. $type$ is a string consisting of an uppercase letter `A`, `B`, or `C`, followed by a digit `1`, `2`, or `3`. It can help you get partial scores. You may not need to use this parameter. Its meaning is described in detail in the “Data Scale and Conventions” section. The second line contains $n$ integers. The $i$-th integer denotes the cost $p_i$ of stationing an army in city $i$. The next $(n - 1)$ lines each contain two integers $u, v$, indicating a two-way road between $u$ and $v$. The next $m$ lines each contain four integers $a, x, b, y$, describing one requirement: station $x$ armies in city $a$, and station $y$ armies in city $b$. Here, $x, y$ can only be $0$ or $1$: - If $x$ is $0$, city $a$ must not have an army stationed. - If $x$ is $1$, city $a$ must have an army stationed. - If $y$ is $0$, city $b$ must not have an army stationed. - If $y$ is $1$, city $b$ must have an army stationed. In the input file, any two adjacent data items on the same line are separated by one space.

Output $m$ lines. Each line contains one integer. The $j$-th line represents the minimum total cost when satisfying the king’s $j$-th requirement. If the king’s $j$-th requirement cannot be satisfied, output $-1$ on that line.

#### Sample 1 Explanation - For the first requirement, the minimum cost is achieved by stationing armies in cities $4$ and $5$. - For the second requirement, the minimum cost is achieved by stationing armies in cities $1$, $2$, and $3$. - The third requirement cannot be satisfied, because not stationing armies in both cities $1$ and $5$ means there exists a road whose two directly connected cities both have no armies stationed. #### Constraints | Test Point ID | $\text{type}$ | $n = m=$ | |:-:|:-:|:-:| | $1,2$ | `A3` | $10$ | | $3,4$ | `C3` | $10$ | | $5,6$ | `A3` | $100$ | | $7$ | `C3` | $100$ | | $8,9$ | `A3` | $2\times 10^3$ | | $10,11$ | `C3` | $2\times 10^3$ | | $12,13$ | `A1` | $10^5$ | | $14, 15, 16$ | `A2` | $10^5$ | | $17$ | `A3` | $10^5$ | | $18,19$ | `B1` | $10^5$ | | $20,21$ | `C1` | $10^5$ | | $22$ | `C2` | $10^5$ | | $23, 24, 25$ | `C3` | $10^5$ | Meaning of the data types: - `A`: City $i$ is directly connected to city $i + 1$. - `B`: The distance from any city to city $1$ is at most $100$ (distance is defined as the number of edges on the shortest path). That is, if the tree is rooted at city $1$, its depth is at most $100$. - `C`: There are no special constraints on the shape of the tree. - `1`: In each query, it is guaranteed that $a = 1, x = 1$, meaning city $1$ must have an army stationed. There are no restrictions on $b, y$. - `2`: In each query, it is guaranteed that $a, b$ are adjacent (directly connected by one road). - `3`: There are no special constraints on the queries. For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 10^5$, $1 \leq p_i \leq 10^5$, $1 \leq u, v, a, b \leq n$, $a \neq b$, and $x, y \in \{0, 1\}$. Translated by ChatGPT 5