提示: 欢迎访问OurACM平台。
Problem 2114 集结

Accept: 19    Submit: 242
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

话说自从奇迹大陆遭受到了来之亡灵位面的亡灵大军的攻击。大陆上各大种族组成了奇迹联盟共同对抗亡灵大军的入侵至今,已经过去了一百多年了。由于,此次亡灵军队是由万年前的巫妖王艾特和数百个巫妖带领的,亡灵军队来势过猛。所以,在这一拜年的战争中,联军并未将亡灵从大陆驱逐出去。反而,联军已经被亡灵大军冲散了。各个势力和城镇都各自为战。

为了改变当前局势,联军总司令LKity决定集结所有的军队,集中力量对抗亡灵大军。为了尽量减少军队集结过程中军队的损失和尽早的完成集结行动,LKity必须选择一座城镇作为集结点。为此,LKity烦恼了好久。你是否能帮帮这只可爱的Kity猫吗?

联军的军队坐落于N(1<=N<=100,000)座城镇中,每座城镇拥有ai(0<=i<N)个士兵。由于,战争区间,大部分道路都被亡灵大军破坏掉了。所以,在这N座城镇间只有N-1条道路。不过幸运的是各城镇能通过这些道路到达任意的其他城镇。在这些道路中,有的道路分散着失散的联军小队,也有的是分散着亡灵大军。集结命令下达后,各城镇的军队将立即往集合城市以最短的路径行进。在集结过程中,如果联军的军队遇到了我军失散的小队,可以收编这些小队。如果遇到的是亡灵军队,则必须消灭所有亡灵才能通过这条道路。在消灭过程中,我军将损失与亡灵军队同等数量的士兵。当然,如果我军士兵比亡灵少,那我军将全军覆没,同时,亡灵军队将损失我军的士兵数量。

为了简便,联军部队从一个城镇到另外一个城镇将发挥一个月的时间,不管路上遇到的是联军的小队还是亡灵军队。注意哦,失散的小队是不能接收到联军总司令LKity的命令的。请你选择一座城镇作为集结点,使得集结后军队的数量最大。如果军队数量一样,则选择集结花费时间最少的。

Input

输入为标准输入,输入数据中有多组数据,每组数据格式如下:

第一行为一个正整数N(1<=N<=100,000)表示奇迹大陆上的城镇数。

接下来一行包含N个整数ai(0<=i<N,0<=ai<=100,000),表示该城镇有ai个人。如果ai=0则表示该城为空城。

接下来有N-1行,每行3个整数a,b,c分别表示有一条道路连接着城镇a和城镇b,道路中分散着c个士兵。(0<=a,b<N,-100,000<=c<=100,000)如果c小于0 表示该道路上分散着|c|个亡灵,如果c>0表示该道路上分散着c个联军士兵

Output

对于每组数据,请在一行中输出两个整数count和 time。其中count表示集结后联军的军队数量,time表示集结所花费的时间.用空格隔开

Sample Input

3 1 2 3 0 2 1 0 1 -1

Sample Output

6 1

Source

FOJ有奖月赛-2013年4月(校赛热身赛)

Submit  Back  Status  Discuss