building2 - ビルの飾り付け 2 Editorial /

Time Limit: 1 sec / Memory Limit: 64 MiB

配点 : 100 点

問題文

日本には N 個の街があり,それらの間は N - 1 本の双方向に通行可能な道路で結ばれている.どの街からどの街へもいくつかの道路をたどって行くことができる.各街には役所のビル 1 つがあり,街 i のビルの高さを H_{i} とする.

国際情報オリンピックが日本で開かれるに伴い,世界の選手達を歓迎するため,観光ツアーを計画しようとしている.観光ツアーは,ある街からスタートし,道路をたどって違う街へ移動することを繰り返し,ある街で終了する.この時,同じ街を 2 度以上訪れることはないようにすることとなっている.

世界の選手たちをより一層歓迎するため,観光で訪れるうちの一部の街の役所のビルを飾り付けることにした.ある著名なデザイナーにデザインを依頼したところ,飾りつけに利用するビルは,出発する街から到着する街に向けて高くなっていく必要があると言った.つまり,役所のビルを飾り付けることにした街を i_{1}, i_{2}, \ldots, i_{k} とおき,観光ツアー中にこれらの街を i_{1}, i_{2}, \ldots, i_{k} という順番で訪れるとしたとき,ビルの高さが H_{i_{1}} < H_{i_{2}} < \cdot \cdot \cdot < H_{i_{k}} となっていなければならない.(全ての訪れる街のビルを飾り付けなければならないわけではないことに注意せよ.)

課題

できるだけ飾りつけを華やかにするため,飾りつけに利用するビルの数をできるだけ多くしたい.開始する街,終了する街,ビルの飾り付けをする街を自由に選べるとしたとき,飾りつけに利用することのできるビルの数の最大値を計算するプログラムを作れ.

制約

  • 2 \leqq N \leqq 100\,000:街の数.
  • 1 \leqq H_i \leqq 1\,000\,000\,000:街 i のビルの高さ.

入力

標準入力から以下の入力を読み込め.

  • 1 行目には整数 N が書かれており,街の数を表す.
  • 続く N 行には,各街の役所のビルの高さに関する情報が与えられる.これらの行のうちの i 行目には整数 H_{i} が書かれている.これは街 i のビルの高さが H_{i} であることを表す.
  • 続く N - 1 行には,道路に関する情報が与えられる.これらの行のうちの i 行目には整数 A_{i}, B_{i} (1 \leqq A_{i} < B_{i} \leqq N) が空白を区切りとして書かれている.これは i 番目の道路が街 A_{i} と街 B_{i} を結んでいることを表す.

出力

標準出力に,飾りつけに利用することのできるビルの数の最大値を表す整数を出力せよ.

採点基準

採点用データのうち,配点の 10\% 分については N \leqq 100 を満たす.

採点用データのうち,配点の 30\% 分については N \leqq 2\,000 を満たす.

入出力例

入力例 1

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

出力例 1

4

Source Name

JOI 2011-2012 春季トレーニング合宿 Contest Day1