见 https://www.luogu.com.cn/problem/U369959 仅有数据范围不同：

题目背景

在七万五千米的高空，“阿特拉哈西斯的方舟”之上——

“阿拜多斯小队到达指定位置！接触‘连接装置！’”

“邦巴卡邦！爱丽丝已到达西侧魔王城！光之剑，充能完毕！”

为了争取唤起奇迹的五秒钟，阿拜多斯剩余的三人、千年科技学院的游戏开发部四人，分别奔赴“方舟”东西两侧的连接装置处。

“连接装置的分布构造......是树形图？”

“大叔这边也确认了，也是树形图呢，真是麻烦的东西啊......”

“姐姐，阿拜多斯那边的树形图构造和我们这边同构，并且，这种分布式构造有点特殊......”

经过分析，树形图的每个结点对应一个装置，其中也含有一些特殊构造——

“可以分析出来，每个装置都带有一定量的能量，其坚固程度好像也和能量相关......”

“爱丽丝分析完成！这些BOSS之间有紧密联系和特殊技能，勇者并不能直接对某个BOSS造成伤害，但是，从第二次攻击开始，如果伤害足够，可以将外面连接的一圈BOSS全部消灭掉！”

“接下来，这些装置们好像会某种从属关系，每次攻击某个装置时，到第一个被攻击的装置的路径上所有装置不会受影响......”

“爱丽丝明白，以第一个被攻击的BOSS为中心，外侧的BOSS归属于内侧的BOSS，并且每个BOSS只有一个直属头领！”

“并且，这些装置之间的能量不太稳定......承担装置防守的能量来源时直属于它下层的装置，但是每次供能的时候，如果有不同能量团，貌似能量是数值最小那个提供......”

“每当一个BOSS受到的攻击伤害超过防守它的所有魔力的总和的时候，它所有的直接下属的BOSS就会被消灭掉！但委托没有完成！它会接收所有被击败的下属的魔力瓶，并将它们的下属收入麾下！”

“并且，当只剩下一个装置时，由于能量相互作用，它好像会自行崩坏......”

“呜呜，大叔似乎听不太懂这些呢......芹香酱，野宫酱，你们知道怎么打吗......”

“总之想办法让总体的输出能量消耗最少就可以了吧！！！”

“芹香酱说的没错，毕竟消耗武器能量会影响效率，要尽早帮上白子酱和Sensei......”

“爱丽丝的光之剑，准备就绪！”

“等等爱丽丝！先不要动手！”

“怎么了吗小绿？爱丽丝有把握将这些阻拦我们的魔王一剑......”

“要求是'同时破坏'。我对爱丽丝的战斗力很放心，但是另一边......”

“欸！？她们只有突击步枪、机枪和霰弹枪吗？没有重火力！？”

“爱丽丝明白，要和其他勇者一同协作，齐心协力救出sensei！爱丽丝随时待命！”

“......千年的小妹妹们，你们能算出来，一开始攻击哪里可以让总耗能最少吗？把位置和总耗能告诉大叔，剩下的就交给我们吧。”

“明白！不过......这怎么算？小绿你会吗？”

“我之前没在sensei那里学过处理这种问题，他也没有在和我单独的时候讲过。”

“爱丽丝，可以提供算力！请告诉爱丽丝计算方法，爱丽丝马上算出来告诉东边的勇者们！”

“啊啊啊，早知道就不在算法课上跑神思考策划了！苦呀西，苦呀西！！！”

“给定一颗 $n$ 个结点的树，每个结点上有可重的正整数集合，初始时每个结点的集合中有一个正整数，在确定根之后，可以对某个结点进行操作，代价是它每个儿子的集合中最小值之和，效果是，将所有儿子删除，儿子的集合中的所有数转移到自身集合上，并且将儿子的儿子变为自己的儿子。目的是，让整颗树只剩下一个结点，并且让总代价最小。想想，UZQueen的话......玩过类似的解密游戏......！！！” "爱丽丝......我明白了。"

“嗯，交给柚子了！”

题目描述

防止有人眼瞎再发一遍。

给定一颗 $n$ 个结点的树，每个结点上有可重的正整数集合，初始时每个结点的集合中有一个正整数，在确定根之后，可以对某个结点进行操作，代价是它每个儿子的集合中最小值之和，效果是，将所有儿子删除，儿子的集合中的所有数转移到自身集合上，并且将儿子的儿子变为自己的儿子。现在要求是，找到一个根，之后通过若干次操作让整颗树只剩下一个结点，且所有操作总代价最小。若存在多个满足要求的结点，其编号应当最小。

输入格式

从文件kiseki.in中读入数据。

第一行一个正整数 $n$ 表示树的结点个数。

接下来一行 $n$ 个正整数以空格隔开表示每个结点的初始能量。

接下来 $n-1$ 行，每行两个数 $u,v$ 代表结点 $u$ 与结点 $v$ 之间存在连边。保证给出的是一颗树。

本题保证每个点的初始能量不超过 $5\times 10^5$。

输出格式

输出到文件kiseki.out中。

输出一行两个正整数，以空格隔开。

第一个正整数表示此时选择的第一个攻击的结点，第二个正整数表示此时完成对整个连接装置的攻击所需的最小攻击能量输出。

样例 #1

样例输入 #1

6
1 1 4 5 1 4
1 6
2 6
4 3
1 3
5 6

样例输出 #1

4 5

提示

记第 $i$ 个结点的初始能量值为 $a_i$ ，本题保证$\forall i \in[1,n],1 \le a_i \le 2\times 10^6$ 。

测试点编号	$n\le$	特殊性质
1-2	$10$	无
3-4	$500$
5-6	$2\times 10^3$
7-8	$5\times 10^5$	树的形态是菊花
9-10	$5 \times 10^5$	树的形态是链
11-14	$5\times 10^5$	无
15-20	$2 \times 10^6$