{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"在大家的三连助攻下,TT 一举获得了超级多的猫咪,因此决定开一间猫咖,将快乐与大家一同分享。并且在开业的那一天,为了纪念这个日子,TT 在猫咖门口种了一棵苹果树。\n\n一年后,苹果熟了,到了该摘苹果的日子了。\n\n已知树上共有 N 个节点,每个节点对应一个快乐值为 w[i] 的苹果,为了可持续发展,TT 要求摘了某个苹果后,不能摘它父节点处的苹果。\n\nTT 想要令快乐值总和尽可能地大,你们能帮帮他吗?"}},{"title":"Input","value":{"format":"MD","content":"结点按 1~N 编号。\n\n第一行为 N (1 ≤ N ≤ 6000) ,代表结点个数。\n\n接下来 N 行分别代表每个结点上苹果的快乐值 w[i](-128 ≤ w[i] ≤ 127)。\n\n接下来 N-1 行,每行两个数 L K,代表 K 是 L 的一个父节点。\n\n输入有多组,以 0 0 结束。"}},{"title":"Output","value":{"format":"MD","content":"每组数据输出一个整数,代表所选苹果快乐值总和的最大值。"}},{"title":"输入样例","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e7\n1\n1\n1\n1\n1\n1\n1\n1 3\n7 4\n2 3\n4 5\n6 4\n3 5\n0 0\n\u003c/pre\u003e"}},{"title":"输出样例","value":{"format":"MD","content":"\u003cpre class\u003d\"sio\"\u003e5\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"MD","content":""}}]}