Building 2(ビルの飾り付け 2) - joi2012-day1

出典: 第11回日本情報オリンピック 日本代表選手選考会

時間制限: 1秒

メモリ制限: 64MB

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

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

世界の選手たちをより一層歓迎するため，観光で訪れるうちの一部の街の役所のビルを飾り付けることにした．ある著名なデザイナーにデザインを依頼したところ，飾りつけに利用するビルは，出発する街から到着する街に向けて高くなっていく必要があると言った．つまり，役所のビルを飾り付けることにした街を i_1, i_2, …, i_k とおき，観光ツアー中にこれらの街を i_1, i_2, …, i_k という順番で訪れるとしたとき，ビルの高さが H_{i_1} < H_{i_2} < … < 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 を満たす．

入出力例

入力例	出力例
7 4 2 5 3 1 8 7 1 2 2 3 3 4 4 5 3 6 6 7	4