3778: 巧克力

    众所周知，Alice 和 Bob 是一对宿敌，每次博弈游戏中 Alice 和 Bob 总绞尽 脑汁企图战胜对手，而且很不公平地，每次都是 Alice 先手。

    然而他们都看上了大 M 种的一棵巧克力树，为了取得更多的巧克力，他们决 定联手合作。

    大 M 的巧克力树由 n 个节点组成，每个节点 i 上都有 v[i]个巧克力，巧克 力树上有 n-1 条树枝连接这整棵树（保证任意两点间存在一条路径）。

    Alice 和 Bob 一开始都可以选择一个出发起点并获得该节点上的所有巧克 力，当然，Alice 先选。接下来，Alice 和 Bob 会依次移动到自己节点相邻的节 点上，并获得该节点上的所有巧克力。但是，任意节点都只能被经过一次，若 Alice 走过某个节点 x，则 Bob 不能到达这个节点，当然 Alice 也不能走回 x。

    请问他们总共最多能获得多少巧克力？

  第一行 1 个整数 n，表示节点个数；

  第二行 n 个整数，表示 v[1..n]；

  接下来 n-1 行，每行两个整数 x 和 y，表示节点 x 与节点 y 之间有一条树枝 相连。

    输出一行一个数，为总共能获得的最多的巧克力数。

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

25