P3576 [POI 2014] MRO-Ant colony

[English Edition](/paste/44plylwf)

正在寻找食物的蚂蚁们来到了一座山。 这座山有 $n$ 个洞穴，并有 $n-1$ 条道路连接这些洞穴。也就是说，所有的洞穴和道路组成了一个树形结构。 对于每个只有一条道路连接的洞穴，都有一个出入口使得该洞穴与外界相连。 在**每个出入口**处，都有 $g$ 群蚂蚁，第 $i$ 群蚂蚁的大小为 $m_i$。 蚂蚁群会一个接一个地进入山中，当且仅当山中没有蚂蚁，下一群蚂蚁才会进入。 进入山后，蚂蚁们会按如下方式行动： - 如果蚂蚁们进入了一个洞穴，该洞穴有 $d$ 条道路与之相连（不包括它们进入该洞穴经过的道路），则蚂蚁们会分为大小相等的 $d$ 个蚁群，每个蚁群各选择一条道路，使得一个道路恰好有一条蚁群经过，特别地，如果 $d=0$（即蚁群到达了出口），蚂蚁们会从该出口离开山。 - 根据上文，假如这个蚁群有 $x$ 只蚂蚁，则每个蚁群会有 $\left \lfloor \dfrac{x}{d} \right \rfloor$ 只蚂蚁，多余的蚂蚁将会消失（至于怎么消失，这并不重要 :)）。 下面这张图就是一个例子：大小为 $m$ 的蚁群到达了一个洞穴，该洞穴有 $3$ 条道路（除了它们进入该洞穴时经过的道路），则该蚁群分割成了三个大小为 $\left \lfloor \dfrac{m}{3} \right \rfloor$ 的蚁群。  在其中一条道路上，有一只食蚁兽，当经过该道路的蚁群大小恰好为 $k$ 时，它会把这个蚁群的蚂蚁全部吃掉。 现在请你求出食蚁兽一共吃掉多少只蚂蚁。

无

无

对于 $100\%$ 的数据，$2\le n,g\le10^6$，$1\le k,m_i\le10^9$，$1\le a_i,b_i\le n$。