小明有一只29级的QQ宠物，他决定在宠物社区里帮助自己的宠物讨好一些NPC获得一定的好感度，小明当然想让自己的宠物获得最大的好感度啦，但他并不能同时讨好两个直接认识的NPC，好消息是只有n-1对NPC直接认识，并且将所有相互认识的NPC连在一起能形成一个树形的结构图。
这时候小红发现了小明的所作所为，QQ宠物只有16级的小红十分看不惯小明的这种行为，于是他又介绍了k对互相不直接认识的NPC互相认识。这下小明大感头疼，随即想出一个妙计，他趁这新认识的k对NPC关系尚未牢固又挑拨了其中k-1对NPC的关系，也就是说当前只有n对NPC互相认识。
但小明还是很头疼，他想知道他通过讨好NPC能获得的最大好感度到底是多少，于是找到了聪明的你，你能帮忙解答一下么?
第一行一个整数n代表社区中NPC的个数。为方便起见这n个NPC由1~N编号。
第二行n个正整数，表示讨好每个NPC能获得的好感度wi(wi≤10000)。
下面n行，每行2个整数x,y，表示x号,y号NPC直接认识。
输出包含一个整数为小明所能为他的宠物争取到的所有好感度之和，求这个和最大是多少
【数据范围与约定】
对于100%的数据，n≤100,000保证x,y≤n。