#4009. [ABC 246] G. Game on Tree 3

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Reqwey

题目描述

有一棵 个节点的有根树, 号点为根节点。第 个节点有一个正整数权值

条边,第 条边连接

Sky390 和 Reqwey 用一颗棋子在这棵树上做游戏。

棋子开始时在 号点。接下来他们重复进行以下操作:

  1. Reqwey 选择一个非根结点,把它的权值修改成
  2. Sky390 把棋子移到它先前所在节点的一个子节点上。
  3. 当棋子挪到叶子节点时,游戏结束(当然,Sky390 也可以选择在任意时刻结束游戏)。

游戏结束时,Sky390 的得分为棋子所在的节点的权值。Sky390 想让自己的得分尽可能大,但是 Reqwey 想让他得分尽可能小。

假设双方都足够聪明,求出 Sky390 的最终得分。

输入格式

  • 第一行一个整数
  • 第二行 个整数 ,两两之间以一个空格隔开
  • 行中,第 行有两个整数 ,以一个空格隔开。

输出格式

输出答案。

样例

样例输入 1

7
2 4 6 5 6 10
1 2
1 3
2 4
2 5
5 6
5 7

样例输出 1

5

样例解释 1

下面是一种可能的情况:

  1. 棋子在第 号节点
  2. Reqwey 改动第 号节点的权值
  3. Sky390 挪动棋子
  4. Reqwey 改动第 号节点的权值
  5. Sky390 挪动棋子
  6. Sky390 结束了游戏

游戏结束时,棋子所在节点 的权值为 ,为 Sky390 的得分。

样例输入 2

30
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62 32 38 84 49 93 53 26 13 25
13 15
14 22
17 24
12 3
4 3
5 8
26 15
3 2
2 9
4 25
4 13
2 10
28 15
6 4
2 5
19 9
2 7
2 14
23 30
17 2
7 16
21 13
13 23
13 20
1 2
6 18
27 6
21 29
11 8

样例输出 2

70

数据范围与提示

  • 给出的边构成一棵树
  • 所有输入数据均为整数