#1693. 森林游戏

    ID: 1693 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1047来源:qoj.ac数据:公开样例树形DP动态规划

森林游戏

森林游戏

题目描述

标题: 森林游戏 - Problem - QOJ.ac

#5092. 森林游戏

Statistics

The problem was used in the following contests:

小 A 和小 B 正在玩游戏。

他们面前有一个有根树森林,每个点 u 有正整数点权 Au。

小 A 和小 B 轮流操作,小 A 先手。当前操作的玩家需要选择恰好一个树根删除,获得它的点权,它的子树成为新的有根树,它的儿子成为新的树根。

所有点都删除后游戏结束,玩家的得分是由他删除的点权和。

两个玩家的目标都是最大化自己的得分,他们都采用最优策略。求最终小 A 的得分。

给定的初始局面包含恰好一棵 n 个点的树,点编号从 1 至 n,点 1 为根。

输入格式

第一行一个正整数 n,表示点数。

第二行 n 个正整数 A1,A2,…,An,表示每个点的点权。

接下来 n−1 行给出了初始局面,每行两个正整数 u,v 表示树中有一条连接 u,v 的边。保证给定的是一棵树。

输出格式

输出一行一个整数,表示最终小 A 的得分。

样例一

input

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

output

7

样例二

见下发文件。

数据范围与约定

对于所有数据,1≤Ai≤109。

子任务编号 n≤ 特殊性质 分值 1 20 无 20 2 1000 20 3 2×105 A 20 4 B 20 5 无 20

  • 特殊性质 A:设 pi 为 i 的父亲,那么对于所有 2≤i≤n 有 Ai≤Api。
  • 特殊性质 B:所有 Ai 在 [1,109] 的整数内等概率随机。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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