Background

The testdata for this problem has been strengthened. If you got AC during the contest, it is recommended to submit again to make sure your solution is correct.

Do not misread the statement!

——command_block “Pre-exam Tips”

In 2021, you participated on Luogu in a contest called EZEC Round 6, which had a tree-building problem. You thought it was very easy and solved it casually. (So if you have not done the problem in the link, go do it now!!!)

Now you are participating in the JROI-3 monthly contest. You feel that building trees is too easy, and you want to delete the tree instead, so the kind problem setter gives you a chance. However, before deleting the tree, djy wants to know the sum of edge weights of the tree.

Problem Description

This is an interactive problem.

There is a weighted tree with $n$ nodes, numbered $1-n$. The degree of each node is known. djy wants to know the sum of the weights of all edges in the tree, but he is too weak and cannot solve such a simple problem, so he throws it to you.

Since you are strong, you are allowed to make some changes to this tree: delete all nodes with degree $1$, and obtain the number of remaining nodes and the degree of each remaining node.

You may ask the interactive library three types of queries:

• For a node that currently exists in the tree, ask for its dfs order$^1$.
• For a pair of nodes that currently exist in the tree, ask for the distance between them$^2$.
• Delete all nodes with degree $1$ in the current tree, delete the edges adjacent to those nodes, and renumber all remaining nodes. It is guaranteed that the remaining nodes will be numbered $1-k$, where $k$ is the number of remaining nodes.

You need to use no more than 142 operations (including submitting the answer), and before the tree is deleted to empty, find the sum of the weights of all edges in the current tree.

Notes:

• dfs order$^1$: The dfs order means the order in which nodes are first visited when performing depth-first search starting from the current node $1$. The dfs order of a tree is not unique. After each deletion operation, the dfs order will be reset. It is guaranteed that the dfs order does not change due to other operations. That is, for two queries asking the dfs order of the same node, if there is no deletion operation in between, the returned value is guaranteed to be the same.
• Distance$^2$: The sum of edge weights along the path between two nodes in the tree. In particular, the distance between two identical nodes is $0$.

Input Format

Interactive Mode.

This problem uses IO interaction.

Before interaction starts, you need to read $n$, the number of nodes in the tree.

In the next line, there are $n$ numbers, representing the degree of each node.

You can make three types of queries:

• dfn u: Query the dfs order of the node with index $u$ in the interactive library. The library returns one integer in a line, which is the dfs order of $u$.

• dis u v: Query the distance between nodes $u$ and $v$ in the interactive library. The library returns one integer in a line, which is the distance between $u$ and $v$.

• del: Ask the interactive library to delete all nodes with degree $1$ and the edges connected to them. The library will renumber the nodes and rerun a dfs order. The library returns: the first line is one integer, the size of the tree $m$; the second line contains $m$ integers, where the $i$-th integer is the degree of the node numbered $i$.

If you have found the sum of the weights of all edges in the current tree, output the answer $x$ in the format ! x, and terminate the program immediately.

Please ensure that any node used as a query parameter has not been deleted, and that after a del operation the tree is not empty.

If your operation is illegal or the number of operations exceeds 142, the interactive library will terminate the program immediately, and the result will be judged as WA/RE/TLE/MLE.

After each query, do not forget to output a newline and flush the buffer, otherwise unknown errors may occur. To avoid this, you may use:

• For C++, use fflush(stdout) or cout.flush().
• For Java, use System.out.flush().
• For Python, use stdout.flush().
• For other languages, please read related documents.

Output Format

See Interactive Mode.

6
3 1 2 1 1 2

1

5

dfn 1

dis 6 2

! 17

Hint

The sample is only for understanding the interaction process, and may not be logically consistent.

[Sample Explanation]

The shape of the tree is shown above.

In the first query, the dfs order of node $1$ is $1$.

In the second query, the distance between node $2$ and node $6$ is $5$.

The sum of the weights of all edges in the current tree is $17$.

[Constraints]

This problem uses bundled test.

• Subtask 1 (1 pts): $n \le 2$.
• Subtask 2 (4 pts): $n \le 4$.
• Subtask 3 (20 pts): $n\le 150$.
• Subtask 4 (10 pts): The tree is a chain.
• Subtask 5 (30 pts): It is guaranteed that the number of nodes with degree $1$ is at most $50$.
• Subtask 6 (20 pts): $n\le 2000$.
• Subtask 7 (15 pts): No special restrictions.

For $100\%$ of the data, $1\le n\le 5000$, the weight of each edge is at most $10^5$ and is a positive integer.

If any incorrect solution passed, please send a private message to the problem setter to strengthen the testdata. (A hack would be even better.)

Translated by ChatGPT 5