T177352 NOI2021 SDPTT D2T1 我已经完全理解了 DFS 序线段树

题目来源：2021山东省队一轮集训D2T1。 原题编译选项：```-lm -O2 -std=c++11```

给定一棵有 $n$ 个结点的有根树，根结点为 $1$ 号点。 每个点有权值 $a_i$，初始时均为 $0$，以及花费 $v_i$，表示对它进行一次操作时要花费的代价。 对点 $u$ 进行一次参数为 $x$ 的操作，即是在树中将它子树中的所有点的权值都加上 $x$。 要让**每个叶子**的权值互不相同且非零，即当 $i,j(i\neq j)$ 为叶子时要满足 $a_i\neq 0$ 且 $a_i\neq a_j$。 你需要构造一个总花费尽量小的操作序列。

无

无

### 【样例 2】 见附件，该样例满足特殊限制 A（具体限制见数据范围与提示）。 ### 【数据范围与提示】 对于所有测试点：$2\leq n\leq 2 \times 10^5，1\leq v_i\leq 10^9$。 每个测试点的具体限制见下表： | 测试点编号 | $n\leq$ | 特殊限制 | | :----------: | :----------: | :----------: | | $1 ∼ 4$ | $18$ | 无 | | $5 ∼ 6$ | $2\times 10^5$ | $A$ | | $7 ∼ 9$ | $2\times 10^5$ | $B$ | | $10 ∼ 13$ | $2\times 10^5$ | $C$ | | $14 ∼ 25$ | $2\times 10^5$ | 无 | 特殊性质 $A$：结点 $1$ 的度数为 $n-1$； 特殊性质 $B$：结点 $1$ 的孩子结点集为 $\{2,3,...,1000\}$ 且编号大于 $1000$ 的结点均为叶子结点； 特殊性质 $C$：结点 $i$ 的两个孩子（如果编号在范围内）分别为 $2i$ 和 $2i+1$。 出题人：[小粉兔](https://www.luogu.com.cn/user/10703) 上传者：[do_while_true](https://www.luogu.com.cn/user/223298)