← 返回题目列表

AtCoder · joisc2012_building2

building2. 建筑装饰2

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

ビルの飾り付け 2 - 原题 PDF 第 1 页
原题PDF第1页
ビルの飾り付け 2 - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                        Contest Day 1 – Building 2

            ビルの飾り付け2 (Building 2)


 日本にはN 個の街があり,それらの間はN −1 本の双方向に通行可能な道路で結ばれている.どの街か
らどの街へもいくつかの道路をたどって行くことができる.各街には役所のビル1 つがあり,街i のビル
の高さをHi とする.
 国際情報オリンピックが日本で開かれるに伴い,世界の選手達を歓迎するため,観光ツアーを計画しよ
うとしている.観光ツアーは,ある街からスタートし,道路をたどって違う街へ移動することを繰り返し,
ある街で終了する.この時,同じ街を2 度以上訪れることはないようにすることとなっている.
 世界の選手たちをより一層歓迎するため,観光で訪れるうちの一部の街の役所のビルを飾り付けること
にした.ある著名なデザイナーにデザインを依頼したところ,飾りつけに利用するビルは,出発する街か
ら到着する街に向けて高くなっていく必要があると言った.つまり,役所のビルを飾り付けることにした
街をi1, i2, . . . , ik とおき,観光ツアー中にこれらの街をi1, i2, . . . , ik という順番で訪れるとしたとき,ビルの
高さがHi1 < Hi2 < · · · < Hik となっていなければならない.(全ての訪れる街のビルを飾り付けなければな
らないわけではないことに注意せよ.)


課題

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


制限

   2 ≦N ≦100 000    街の数
   1 ≦Hi ≦1 000 000 000 街i のビルの高さ


入力

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

   • 1 行目には整数N が書かれており,街の数を表す.
   • 続くN 行には,各街の役所のビルの高さに関する情報が与えられる.これらの行のうちのi 行目に
   は整数Hi が書かれている.これは街i のビルの高さがHi であることを表す.

   • 続くN −1 行には,道路に関する情報が与えられる.これらの行のうちのi 行目には整数Ai, Bi
      (1 ≤Ai < Bi ≤N) が空白を区切りとして書かれている.これはi 番目の道路が街Ai と街Bi を結んで
   いることを表す.




                    ビルの飾り付け2– 1 / 2

Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                        Contest Day 1 – Building 2


出力

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


採点基準

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


入出力例

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





                    ビルの飾り付け2– 2 / 2