## 题目描述 X 国遭受了地震的重创, 导致全国的交通近乎瘫痪，重建家园的计划迫在眉睫。X 国由 $N$ 个城市组成, 重建小组提出，仅需建立 $N-1$ 条道路即可使得任意两个城市互相可达。于是，重建小组很快提出了一个包含 $N-1$ 条道路的方案，并满足城市之间两两可达，他们还计算评估了每条道路 $e$ 建设之后可以带来的价值 $v(e)$。 由于重建计划复杂而艰难，经费也有一定限制。因此，政府要求第一期重建工程修建的道路数目为 $k$ 条，但需满足 $L \leq k \leq U$，即不应少于$L$ 条，但不超过 $U$ 条。同时，为了最大化利用率，要求建设的这些道路恰好组成一条简单路径，即所建设的 $k$ 条路径可以构成一个排列 $e_1 = (p_1, q_1), e_2 = (p_2, q_2), \cdots , e_k = (p_k, q_k)$， 对于 $1 \leq i