题解 - [CodeForces 1637 F] Towers

发表于 更新于 分类于 ， 本文字数： 601 阅读时长 ≈ 2 分钟

题目链接

原始题面

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given a tree with \(n\) vertices numbered from \(1\) to \(n\). The height of the \(i\)-th vertex is \(h_i\). You can place any number of towers into vertices, for each tower you can choose which vertex to put it in, as well as choose its efficiency. Setting up a tower with efficiency \(e\) costs \(e\) coins, where \(e > 0\)

It is considered that a vertex \(x\) gets a signal if for some pair of towers at the vertices \(u\) and \(v\) (\(u \neq v\), but it is allowed that \(x = u\) or \(x = v\)) with efficiencies \(e_u\) and \(e_v\), respectively, it is satisfied that \(\min(e_u, e_v) \geq h_x\) and \(x\) lies on the path between \(u\) and \(v\)

Find the minimum number of coins required to set up towers so that you can get a signal at all vertices

Input

The first line contains an integer \(n\) (\(2 \le n \le 200\,000\)) — the number of vertices in the tree

The second line contains \(n\) integers \(h_i\) (\(1 \le h_i \le 10^9\)) — the heights of the vertices

Each of the next \(n- 1\) lines contain a pair of numbers \(v_i, u_i\) (\(1 \le v_i, u_i \le n\)) — an edge of the tree. It is guaranteed that the given edges form a tree

Output

Print one integer — the minimum required number of coins Examples

Input

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

Output

1
4

Input

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

Output

1
7

Input

1
2
3
2
6 1
1 2

Output

1
12

Note

In the first test case it's optimal to install two towers with efficiencies \(2\) at vertices \(1\) and \(3\)

In the second test case it's optimal to install a tower with efficiency \(1\) at vertex \(1\) and two towers with efficiencies \(3\) at vertices \(2\) and \(5\)

In the third test case it's optimal to install two towers with efficiencies \(6\) at vertices \(1\) and \(2\)

题意简述

在一棵无根树上放若干个塔，每个塔有权值 \(e\), 树上结点自带权值 \(h\), 要求树上任意结点均在某两个塔之间的简单路径上，且这两个塔的权值均不小于该结点的权值，求塔权值的最小和

解题思路

显然塔应都放在叶子结点上

为方便起见，我们让权值最大的点为根节点，令其为 \(r\), 此时我们只需让叶子结点里有两个塔的权值为 \(h_r\) 即可

我们考虑一条从根节点到叶子结点的链，其中根结点的一端相当于有了一个权值为 \(h_r\) 的塔，那么另一端只需放一个权值为该链上的结点权值次大值的塔即可

这有 2500 ?

复杂度

\(O(n)\)

代码参考

Show code

CodeForces_1637Fview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 2e5 + OFFSET, M = 4e5 + OFFSET, K = 21;
struct Edge {
  int to, next;
  Edge(int _to = 0, int _next = 0): to(_to), next(_next) {}
} e[M];
int head[N], cnt_edge;
void addEdge(int x, int y) {
  e[++cnt_edge] = Edge(y, head[x]);
  head[x] = cnt_edge;
}
#define _for_graph(head, e, i, now) \
  for (int i = head[now], to = e[i].to; i; to = e[i = e[i].next].to)
i64 h[N];
i64 ans;
i64 dfs(int now, int fa = 0) {
  i64 h_son_max = 0, h_son_submax = 0;
  _for_graph(head, e, i, now) {
    if (to == fa) continue;
    i64 _h_max_from_son = dfs(to, now);
    if (_h_max_from_son > h_son_max) {
      h_son_submax = h_son_max;
      h_son_max = _h_max_from_son;
    } else if (_h_max_from_son > h_son_submax) h_son_submax = _h_max_from_son;
  }
  ans += max(i64(0), h[now] - h_son_max + (!fa) * (h[now] - h_son_submax));
  return max(h[now], h_son_max);
}
void solve() {
  int n;
  cin >> n;
  _for(i, 1, n) cin >> h[i];
  int root = 1;
  _for(i, 1, n)
    if (h[root] < h[i]) root = i;
  _for(i, 1, n - 1, x, y) {
    cin >> x >> y;
    addEdge(x, y);
    addEdge(y, x);
  }
  dfs(root);
  cout << ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}