poj2182 树状数组

题目链接：[POJ2182](http://poj.org/problem?id=2182)

题目大意：给定一棵 $n$ 个结点的树，每个结点有一个权值 $w_i$。定义一个结点的价值为它到根结点路径上权值的最小值，求所有结点的价值之和。

思路：我们可以用树状数组来维护每个结点的价值，具体的实现方式如下：

1. 首先对树进行 DFS 遍历，求出每个结点的深度 $dep$ 和在 DFS 序列中的位置 $pos$。

2. 定义一个数组 $f$，其中 $f_i$ 表示以结点 $i$ 为根结点的子树中，所有结点的价值之和。显然，根结点的价值就是它本身的权值。

3. 对于每个结点 $i$，我们需要求出它的父结点 $fa_i$ 的价值。假设 $mindep$ 表示 $i$ 到根结点路径上的最小深度，那么 $fa_i$ 的价值就是 $\min(w_i, f_i + w_{fa_i})$。其中，$w_i$ 表示结点 $i$ 的权值，$f_i$ 表示以结点 $i$ 为根结点的子树中，所有结点的价值之和。

4. 对于每个结点 $i$，我们要将其价值加入到树状数组中，同时更新 $f_{i}$。

5. 最后，树中所有结点的价值之和就是树状数组中存储的所有值的和。

代码实现：