P4312 [COI 2009] OTOCI

Note: The original problem is interactive and enforces online processing. In this version, you do not need to consider interaction.

Not long ago, Mirko founded a travel agency called “Polar Dream.” The agency bought $n$ islands near the Arctic and offers sightseeing services. The most popular attraction is, of course, the emperor penguins. These little fellows often move in groups between the islands. Mirko’s agency suffered a major setback, making cruise tours no longer cost-effective. The agency will build bridges between islands and use sightseeing buses to carry tourists. Mirko wants to develop a computer program to manage the bridge-building process to avoid unexpected errors. The islands are labeled from $1$ to $n$. Initially, there are no bridges between islands, and the number of emperor penguins on each island is known. Although the number on each island may change, it is always within $[0, 1000]$. Your program must process the following three commands: - `bridge u v`: Ask whether nodes $u$ and $v$ are connected. If they are, output `no`; otherwise output `yes`, and add an undirected edge between $u$ and $v$. - `penguins u x`: Set the weight $w_u$ of node $u$ to $x$. - `excursion u v`: If nodes $u$ and $v$ are not connected, output `impossible`. Otherwise, output the sum of the weights of the nodes on the path from $u$ to $v$. There are $q$ operations in total.

- The first line contains an integer $n$, the number of nodes. - The second line contains $n$ integers; the $i$-th integer is the initial weight $w_i$ of node $i$. - The third line contains an integer $q$, the number of operations. - Each of the next $q$ lines contains one operation as described above.

Output the results of all `bridge` and `excursion` operations, one answer per line.

Constraints For $100\%$ of the testdata, $1 \le n \le 3 \times 10^4$, $1 \le q \le 3 \times 10^5$, $0 \le w_i \le 1000$. Translated by ChatGPT 5