题目描述

题目译自 XXI Olimpiada Informatyczna — III etap Zadanie Mrowisko

一群蚂蚁闯入废弃的蚁巢，搜寻食物。蚁巢由 $n$ 个巢室和 $n-1$ 条通道组成，任意两巢室间有唯一路径，构成一棵树。所有只有一条通道的巢室是蚁巢入口。在每个入口，排列着 $g$ 群蚂蚁，分别有 $m_1, m_2, \ldots, m_g$ 只蚂蚁。每群蚂蚁单独进入，下一群需等巢内清空后进入。蚂蚁在巢内按以下规则移动：

• 进入一个有 $d$ 条未访问通道的巢室，蚂蚁群分成 $d$ 个等量小组，每组沿一条通道前进。若 $d=0$，蚂蚁群直接离开蚁巢。
• 若无法均分，强壮蚂蚁会吃掉弱小者，直到能均分成等量小组（甚至可能自我吞噬消失）。

某条通道上方有个洞，潜伏着饥饿的食蚁兽的长舌，它会吞噬恰好有 $k$ 只蚂蚁的经过群体。请你计算食蚁兽能吃掉多少只蚂蚁。

输入格式

输入第一行包含三个整数 $n, g, k$ $(2 \leq n, g \leq 1000000, 1 \leq k \leq 10^9)$，分别表示巢室数、每个入口的蚂蚁群数和食蚁兽吞噬的蚂蚁群规模。巢室编号为 $1$ 到 $n$。

第二行包含 $g$ 个整数 $m_1, m_2, \ldots, m_g$ $(1 \leq m_i \leq 10^9)$，$m_i$ 表示第 $i$ 群蚂蚁的数量。

接下来的 $n-1$ 行描述通道，每行两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n)$，表示 $a_i$ 号和 $b_i$ 号巢室间有通道。食蚁兽的舌头位于第一个输入的通道。

输出格式

输出一行，一个整数，表示食蚁兽吃掉的蚂蚁总数。

7 5 3
3 4 1 9 11
1 2
1 4
4 3
4 5
4 6
6 7

21

入口巢室为 $2, 3, 5, 7$ 号，每处有 $5$ 群蚂蚁。食蚁兽在通道 $1-2$，吞噬：从 $2$ 号入口第一群的 $3$ 只蚂蚁，以及从 $3, 5, 7$ 号入口的第四、第五群各 $3$ 只蚂蚁，共 $21$ 只。

附加样例

1. $n=20, g=20, k=5$，蚁巢为长隧道，食蚁兽舌头在端点通道，群规模为 $1, \ldots, 20$；
2. $n=2^{19}+1, g=20, k=1$，巢室 $1$ 连 $n$（食蚁兽在此通道），巢室 $i$ $(i=2,3,\ldots,n-1)$ 连 $\lfloor i/2 \rfloor$，群规模为 $2^0, 2^1, \ldots, 2^{19}$。

数据范围与提示

对于 $20\%$ 的数据，$n, g \leq 100$。
对于 $50\%$ 的数据，所有入口的蚂蚁群总数不超过 $1000000$。