### 问题描述 城市中建造了 $n$ 个房屋，房屋的编号从 $1$ 到 $n$，房屋间的修建了一些道路，每条道路的长度均为 $1$，房屋和道路共同组成一个树。 现在城市规划中心打算把城市分为多个区，要求每个区中的房屋之间的最长距离不超过 $k$。 每划分一个区需要投入资金 $x$，城市规划中心请你帮忙求出最少投入资金可以完成分区。 ### 输入格式 输入第一行包含三个整数 $n,k,x$，含义见上文。 接下来的 $n-1$ 行，每行包含 $2$ 个整数 $u,v$，表示房屋 $u$ 和房屋 $v$ 之间有一条道路。 ### 输出格式 输出一个整数，表示最少投入的资金。 ### 样例输入 ``` 5 3 3 1 2 2 3 3 4 4 5 ``` ### 样例输出 ``` 6 ``` ### 评测数据规模 对于所有评测数据，$3\leq{n}\leq{10^6 },1\leq{k}\leq{10^6 },1\leq{x}\leq{1000}$。