以下是来自日本的原始新闻PDF,已完整保存和染色。



可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Construction of Highway
高速道路の建設(Construction of Highway)
JOI 王国にはN 個の都市があり,1 からN までの番号が付けられている.都市1 は首都である.各都市
には活気と呼ばれる値が存在し,都市i (1 ≦i ≦N) の活気の初期値はCi である.
JOI 王国の道路は,2 つの異なる都市を双方向に結ぶ.JOI 王国にははじめ,道路は存在しない.JOI 王
国はこれからN −1 本の道路からなる道路網の建設を行う.j 回目(1 ≦j ≦N −1) の道路の建設は以下の
ようにして行われる.
• 都市A j と都市Bj が指定される.このとき,都市1 から幾つかのその時点で建設されている道路を
経由することで,都市A j へは到達可能であり,都市Bj へは到達可能でない.
• 都市A j と都市Bj を結ぶ道路を建設する.このとき,以下の条件を満たす都市の組(s, t) の数だけコ
ストがかかる.
都市s と都市t は都市1 と都市A j を結ぶ最短のパス上に存在し,都市1 から都市A j に行
く際に都市s に都市t より先に到達し,都市s の活気の値が都市t の活気の値より真に大
きい.
ここで,都市1 と都市A j を結ぶパス上の都市には,都市1 と都市A j 自身も含むとする.なお,都
市1 と都市A j を結ぶ最短のパスは,ただ1 つ存在することに注意せよ.
• 都市1 と都市A j を結ぶ最短のパス上に存在するすべての都市について,その活気の値が都市Bj の
活気の値に変化する.
それぞれの道路の建設にかかるコストを知りたい.
課題
都市と道路の建設計画の情報が与えられたとき,それぞれの道路の建設にかかるコストを求めるプログ
ラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数N が書かれている.これはJOI 国にN 個の都市が存在することを表す.
• 2 行目にはN 個の整数C1,C2, · · · ,CN が空白を区切りとして書かれている.これらは都市i(1 ≦i ≦N)
の活気の初期値がCi であることを表す.
• 続くN −1 行のうちのj 行目(1 ≦j ≦N −1)には2 個の整数A j, Bj が空白を区切りとして書かれ
ている.これらはj 回目の道路の建設において都市A j と都市Bj が指定されることを表す.
高速道路の建設– 1 / 3
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Construction of Highway
出力
標準出力にN −1 行で出力せよ.N −1 行のうちのj 行目(1 ≦j ≦N −1) には,j 回目の道路の建設にか
かるコストを出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦100 000.
• 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦N).
• 1 ≦A j ≦N (1 ≦j ≦N −1).
• 1 ≦Bj ≦N (1 ≦j ≦N −1).
• j 回目より前に建設された道路を用いて,都市1 から都市Aj へは到達可能であり,都市Bj へは到
達可能でない(1 ≦j ≦N −1).
小課題
この課題では小課題は全部で3 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [7 点]
• N ≦500.
小課題2 [9 点]
• N ≦4000.
小課題3 [84 点]
追加の制限はない.
高速道路の建設– 2 / 3
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Construction of Highway
入出力例
入力例1 出力例1
5 0
1 2 3 4 5 0
1 2 0
2 3 2
2 4
3 5
入力例1 では,以下のように建設が行われる.
• 1 回目の建設では条件を満たす都市s, 都市t の組は存在しないので建設にかかるコストは0 である.
都市1 と都市2 の間に道路ができ,都市1 の活気の値が2 に変わる.
• 2 回目の建設でも建設にかかるコストは0 である.都市2 と都市3 の間に道路ができ,都市1 と都市
2 の活気の値が3 に変わる.
• 3 回目の建設でも建設にかかるコストは0 である.都市2 と都市4 の間に道路ができ,都市1 と都市
2 の活気の値が4 に変わる.
• 4 回目の建設では(s, t) = (1, 3), (2, 3) が条件をみたすので建設にかかるコストは2 である.都市3 と
都市5 の間に道路ができ,都市1 と都市2 と都市3 の活気の値が5 に変わる.
入力例2 出力例2
10 0
1 7 3 4 8 6 2 9 10 5 0
1 2 0
1 3 1
2 4 1
3 5 0
2 6 1
3 7 2
4 8 3
5 9
6 10
高速道路の建設– 3 / 3