#P18690. Is it well known in Poland?

    ID: 18026 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS零和博弈树形 DP左偏树堆合并交换论证奇偶性分析

Is it well known in Poland?

Is it well known in Poland?

这个问题也许在某些国家很有名,但如果没有人把它拿出来出题,其他国家的人又如何知道它呢?

小青鱼(Little Cyan Fish,Xiao Qingyu)和大核仁(Huge Nucleus Kernel,Da Heren)是形影不离的朋友。

2020 年,小青鱼在准备全国信息学奥林匹克竞赛时,尝试了一道来自 Potyczki Algorytmiczne 2010 的有趣题目:

两只白蚁准备吃掉一道旧木栅栏。栅栏由若干高度可能不同的木板组成,它们已经吃掉了其中一些木板。为了让这顿饭更有趣,两只白蚁决定轮流行动,每次吃掉一块木板,而且只能吃与已经被吃掉的木板相邻的木板。假设每只白蚁都希望让自己在整个游戏中吃掉的木板高度之和尽可能大,求最后各自吃掉的木头量。

原题作者:Tomasz Idziaszek。

这道题令小青鱼十分感兴趣,并留下了深刻印象。

现在,小 A 和小 B 进行下面的游戏。有一个有根树森林,每个顶点 uu 有一个正整数点权 aua_u。

小 A 先手,两人轮流操作。轮到的玩家必须选择当前森林中恰好一棵树的根,获得这个顶点的点权,然后删除它。被删除顶点的每个孩子都成为一棵新树的根,原来的后代关系保持不变。玩家可以在不同的树之间自由选择,不能跳过自己的回合。

所有顶点都被删除后,游戏结束。每个人的分数是自己删除的所有顶点的点权之和。

两人都采用最优策略,使自己的最终分数尽可能大。求小 A 的最终分数。

初始状态只有一棵树,共有 nn 个顶点,编号为 11 至 nn,其中顶点 11 是根。

输入格式

第一行包含一个整数 nn(2≤n≤1052\le n\le10^5),表示顶点数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤1091\le a_i\le10^9),其中 aia_i 为顶点 ii 的点权。

接下来 n−1n-1 行,每行包含两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i),表示连接这两个顶点的一条无向边。输入的边构成一棵树。边的方向、顺序与顶点编号不保证是从父亲到孩子的遍历顺序。

本题输入只有一组数据。

输出格式

输出一行一个整数,表示双方最优行动时小 A 的最终分数。

样例 1 输入

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

样例 1 输出

7