登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4105
  • 题目
  • P4105Ant colony
    限制 : 时间限制 : 20000 MS   空间限制 : 165536 KB
    评测说明 : 1s

    The ants are scavenging an abandoned ant hill in search of food. The ant hill has  chambers and  corridors connecting them. We know that each chamber can be reached via a unique path from every other chamber. In other words, the chambers and the corridors form a tree.

    There is an entrance to the ant hill in every chamber with only one corridor leading into (or out of) it. At each entry, there are  groups of  ants respectively. These groups will enter the ant hill one after another, each successive group entering once there are no ants inside. Inside the hill, the ants explore it in the following way:

    • Upon entering a chamber with  outgoing corridors yet unexplored by the group, the group divides into  groups of equal size. Each newly created group follows one of the  corridors. If , then the group exits the ant hill.
    • If the ants cannot divide into equal groups, then the stronger ants eat the weaker until a perfect division is possible. Note that such a division is always possible since eventually the number of ants drops down to zero. Nothing can stop the ants from allowing divisibility - in particular, an ant can eat itself, and the last one remaining will do so if the group is smaller than .

    The following figure depicts  ants upon entering a chamber with three outgoing unexplored corridors, dividing themselves into three (equal) groups of  ants each.

    A hungry anteater dug into one of the corridors and can now eat all the ants passing through it. However, just like the ants, the anteater is very picky when it comes to numbers. It will devour a passing group if and only if it consists of exactly  ants. We want to know how many ants the anteater will eat.


    The first line of the standard input contains three integers  (), separated by single spaces. These specify the number of chambers, the number of ant groups and the number of ants the anteater devours at once. The chambers are numbered from 1 to .

    The second line contains  integers  (), separated by single spaces, where  gives the number of ants in the -th group at every entrance to the ant hill. The  lines that follow describe the corridors within the ant hill; the -th such line contains two integers  (), separated by a single space, that indicate that the chambers no.  and  are linked by a corridor. The anteater has dug into the corridor that appears first on input.

    In tests worth  of the total score, the total number of groups of ants entering the ant hill does not exceed . Moreover, in their subset worth  of the total score, it additionally holds that .


    Your program should print to the standard output a single line containing a single integer: the number of ants eaten by the anteater.


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




    Explanation: Next to each of the chambers no. 2, 3, 5, and 7, there are 5 groups of ants. The anteater will eat 3 ants from the first group that starts its exploration at chamber no. 2 and 3 ants from both the fourth and the fifth group that start their exploration at the chamber no. 3, 5, or 7.

    来源  poi2014 bzoj3872