P7895 『JROI-3』删树

**本题数据已加强，建议场上过了的同学再次提交确定做法正确性。** > 千万不要看错题！ ——command_block 《考前小贴士》 你在 2021 年在洛谷打了一场比赛叫做 EZEC Round 6，其中里面有一道[造树题](https://www.luogu.com.cn/problem/P7390)你觉得特别水，随手就切了它。（所以没做过链接里题的人快来做啊！！！） 现在你在打 JROI-3 的月赛，你觉得造树太水了想删掉树，于是良心的出题人给了你一个机会。但是，在删除树之前，djy 想先知道树的边权和。

**这是一道交互题。** 有一个 $n$ 个节点的带边权的树，编号为 $1-n$。每个点的度数是已知的。djy 想知道树上所有边的权值和，但他太菜了，不会去算如此简单的问题，因此把这个题扔给了您。 由于您很强，所以您可以对这棵树进行一些改变：删除所有度数为 $1$ 的节点，得到剩下点的个数和每个点的度数。 您可以向交互库进行三种类型的提问： - 对于当前树上存在的一个点，询问它的 dfs 序$^1$。 - 对于当前树上存在的一对节点，询问它们之间的距离$^2$。 - 删除当前树上所有度数为 $1$ 的节点，同时删除与这些节点相邻的边，并且将所有未被删除的节点进行重新编号。**保证剩下的节点的编号分别为 $1-k$，其中 $k$ 是剩下的节点个数。** 你需要操作**不超过 142 次（包括提交答案）**，并在树**删空**之前求出**当前**树上所有边的权值和。 --- 注： - dfs 序$^1$：dfs 序指从当前的 $1$ 号节点进行 [深度优先搜索](https://baike.baidu.com/item/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2/5224976) ，每个节点被第一次访问的顺序。一棵树的 dfs 序不唯一。每次删除操作后 dfs 序会被重置。保证 dfs 序不随着其他操作而改变，即两次询问同一节点的 dfs 序的询问中间如果没有删除操作，保证回答相同的值。 - 距离$^2$：指在树上两点路径上的边权和。特别地，两个相同节点的距离为 $0$。

**「交互模式」** **本题采用 IO 交互模式。** 在开始交互前，您需要先读入 $n$，表示树中点的个数。 接下来一行 $n$ 个数，表示每个点的度数。 您可以进行三种类型的询问： - `dfn u`: 询问交互库编号为 $u$ 的节点的 dfs 序。交互库返回一行一个整数，表示 $u$ 的 dfs 序。 - `dis u v`: 询问交互库编号为 $u$ 和 $v$ 的两个节点的距离。交互库返回一行一个整数，表示 $u$ 和 $v$ 的距离。 - `del`: 要求交互库删除度数为 1 的点以及与之相连的边。交互库将对点进行重编号，并重新跑一个 dfs 序，交互库返回第一行一个整数为树的大小 $m$，第二行 $m$ 个整数，第 $i$ 个表示编号为 $i$ 的点的度数。 如果您求出了当前树上所有边的边权和，按照 `! x` 的格式输出答案 $x$，并立刻结束程序。 请保证作为询问参数的节点未被删除且 del 操作后树不为空。 **如果您的操作不合法或次数大于 142 次，交互库会立刻终止程序，并将结果判定为 WA/RE/TLE/MLE。** 在每一次询问之后，请不要忘记输出换行符以及清空缓存区，否则将会出现未知的错误。为了避免这种情况，您可以使用： - 对于 C++，使用 ```fflush(stdout)``` 或 ```cout.flush()```。 - 对于 Java，使用 ```System.out.flush()```。 - 对于 Python，使用 ```stdout.flush()```。 - 对于其他语言，请阅读相关文献。

见 **「交互模式」**。

**样例仅供理解交互过程，可能不符合逻辑。** 【样例解释】  树的形态如上。 第一次询问节点 $1$ 的 dfs 序，为 $1$。 第二次询问节点 $2$ 与节点 $6$ 的距离，为 $5$。 当前树上所有边的边权和为 $17$。 ----- 【数据范围】 **「本题采用捆绑测试」** - Subtask 1（1pts）：$n \le 2$。 - Subtask 2（4pts）：$n \le 4$。 - Subtask 3（20pts）：$n\le 150$。 - Subtask 4（10pts）：树是一条链。 - Subtask 5（30pts）：保证度数为 $1$ 的点不超过 $50$ 个。 - Subtask 6（20pts）：$n\le 2000$。 - Subtask 7（15pts）：无特殊限制。 对于 $100\%$ 的数据，$1\le n\le 5000$，每条边的边权不大于 $10^5$ **且为正整数**。 **如果有假做法过了，请私信联系出题人加强数据。（如果有hack更好了）。**