Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 300 点
問題文
百人一首には「わたのはら」で始まる歌が2首あり、6文字目を聞いて初めて取る札を確定できます。このように、「最初から q 文字目までが百人一首の他のどの歌とも共通しない」を満たす最小の q が p であるとき、その歌は「 p 字決まりである」と言います。例えば、「わたのはら」で始まる2首は6字決まりです。
数学家の高橋くんは、 p 字決まりの概念を拡張した真・ p 字決まりを考えました。ある歌 S が真・ p 字決まりであるとは、以下の条件を満たす最小の q が p であることを指します。
- S のどの長さ q の部分列も、歌集の他の歌の部分列でない
この真・ p 字決まりをさっそく使いたくなった高橋君は、青木さんの歌集「一人二首」の歌で調べることにしました。一人二首は、青木さんの詠んだ2つの歌 S,\ T のみで構成されています。高橋くんに代わって、和歌 S が「一人二首」において真・何字決まりであるか求めなさい。2つの和歌は同一ではないことが保証されます。
部分列とは
ある文字列 s の部分列は、 s の中から連続するとは限らない0個以上の文字を選択して元の順に並べた文字列のことを指します。例えば、rhhanやirohachan、空文字列はirohachanの部分列ですが、takahashikunやnahcahoriはそうではありません。
制約
- S と T は英小文字のみで構成される文字列
- 1 \leq |S|=|T| \leq 5000
- S \neq T
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
和歌 S が真・p 字決まりであるとき、p を1行で出力せよ。
入力例 1
abbcd abccd
出力例 1
5
入力例 2
watanoharayasosimakaketekogiidenuto watanoharakogiidetemirebahisakatano
出力例 2
20
解説
解説Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : \(300\) 点
問題文
いろはちゃんの住んでいる地域は (0,0),(0,Y),(X,0),(X,Y) を四隅とする、2次元座標平面上の長方形領域です。 この地域には、 (0,A),(X,B) を通る直線の形をした川が流れています。 いろはちゃんは、河川敷で変態仮面を目撃しました。 この変態仮面は、 (Sx,Sy) から (Tx,Ty) に一直線に移動しようとしています。 変態仮面が川を飛び越える必要があるかどうか判定してください。
制約
- 入力はすべて整数
- 3 \leq X,Y \leq 1000
- 0 < A,B < Y
- 0 < Sx,Tx < X
- 0 < Sy,Ty < Y
- (Sx,Sy)\neq(Tx,Ty)
- (Sx,Sy),(Tx,Ty) は川の上にない
入力
入力は以下の形式で与えられる。
\(X\) \(Y\) \(A\) \(B\) \(Sx\) \(Sy\) \(Tx\) \(Ty\)
出力
変態仮面が川を飛び越える場合は Yes を、飛び越えない場合は No を1行に出力してください。
入力例 1
4 4 2 2 1 1 2 3
出力例 1
Yes
入力例 2
4 4 1 3 1 2 2 3
出力例 2
No
解説
河川敷の変態仮面-解説Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 300 点
問題文
いつも明るいいろはちゃんには妖怪の友達が N 人います。 i(1 \leq i \leq N) 人目の身長は H_i です。
友達が増えすぎたいろはちゃんは、友達がどんなひとだったか忘れないように、その友達の名前と一緒にどれくらいの身長だったかも覚えようと思っています。
しかし、いろはちゃんの友達は妖怪なので、身長がとても高いひともいれば、とても低い人もいます。
そのため、いろはちゃんは友達の身長の大小関係を維持したまま、出来るだけ小さい数に置き換えて覚えておきたいです。
具体的には、任意の整数の組 (i, j) について H_i \leq H_j \Leftrightarrow X_i \leq X_j を満たすような正整数の列 X_1,X_2,\cdots,X_N であって、その最大値が最小となるようなものを構築したいです。
いろはちゃんの代わりに N 人の友達の身長を置き換えてあげてください。
制約
- 入力はすべて整数
- 1 \leq N \leq 10^5
- 1 \leq H_i \leq 10^9
入力
以下の形式で与えられます。
N H_1 H_2 \vdots H_N
出力
1人目から N 人目まで、身長を置き換えた後の正整数を N 行で出力してください。
入力例 1
3 10 20 30
出力例 1
1 2 3
入力例 2
5 10 20 10 30 55
出力例 2
1 2 1 3 4
入力例 3
2 10000 10000
出力例 3
1 1
解説
解説Time Limit: 2 sec / Memory Limit: 256 MB
配点: 400 点
問題文
※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。
きたむーは家庭菜園が趣味である。きたむーは N 個のポットを所持していて、各ポットには 1～N の番号が振られている。また、水が不足したポットに自動で水が流れるよう、 M 本の水路がポットを繋いでおり、水路 i はポット A_i とポット B_iを繋いでいる。また、水路 i は1秒間に C_i デシリットルの水を双方向に流すことができる。なお、あるポットから異なるすべてのポットに対して、何本かの水路を経由することでたどり着くことができる。
さて、きたむーと彼女の関係は順調に進展し、なんと彼女がきたむーの家に来ることになった。きたむーは自分の家庭的な面を見せるため、いつも以上に丁寧にお花さんたちの世話をしていた。
が、しかし！！！
水の流れをよくするためにと水路を増やしすぎて、非常に不格好であることに気が付いた。このままでは片づけができない人間だと思われてしまう。そこで、以下の点を気を付けていくつかの水路を取り除き、水路の数を最小化することにした。
- あるポットから異なるすべてのポットに対して、何本かの水路を経由することでたどり着くことができる状態を保つ
- 残った各水路に流すことができる水の量の総和を最大化する
あなたはきたむーがどの水路を残したのかふと気になったので、プログラム計算によって求めることにした。
制約
- 入力はすべて整数
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 4 \times 10^5
- 1 \leq A_i,B_i \leq N (1 \leq i \leq M)
- A_i \neq B_i (1 \leq i \leq M)
- 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
- C_i \neq C_j (1 \leq i,j \leq M かつ i \neq j)
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
出力
きたむーが残した水路の番号を昇順かつ改行区切りで出力せよ。
この問題の制約のもとで答えは必ず1つであることが証明できる。(2019/05/01 13:25 追記)
入力例 1
5 10 4 1 45 4 2 48 5 3 72 1 4 93 5 1 32 1 3 56 5 1 38 5 4 41 5 2 6 5 1 19
出力例 1
2 3 4 6
入力例 2
5 8 1 4 72 2 1 52 1 3 10 5 3 7 3 4 37 3 2 47 4 1 82 5 3 57
出力例 2
2 6 7 8
解説
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : \(500\) 点
問題文
いろはちゃんはAとBからなる文字列を叫びました。
その文字列は Aを \(N\) 個とBを \(M\) 個含んだ長さ \(N+M\) の文字列で、最初の文字はA、最後の文字はBでした。
また、その文字列は AAA を(連続する)部分文字列に持つことも分かっています。
いろはちゃんが叫んだ文字列としてありうるものは何通りありますか。ありうるものの個数を \(10^9+7\) で割った余りを求めなさい。
制約
- 入力はすべて整数
- \(1≦N, M≦10^5\)
入力
入力は以下の形式で与えられる。
N\ M
出力
答えを1行で出力しなさい。
入力例 1
4 3
出力例 1
5
条件を満たす文字列は AAAABBB, AAABABB, ABBAAAB, AAABBAB, ABAAABB の \(5\) つです。
入力例 2
3 12
出力例 2
1
条件を満たす文字列は AAABBBBBBBBBBBB のみです。
入力例 3
2 1000
出力例 3
0
条件を満たす文字列は存在しません。
入力例 4
11451 41919
出力例 4
538542250
\(10^9+7\) で割った余りを出力してください。
解説
解説Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 500 点
問題文
物理好きさんとひらきちさんは大人気音楽ゲーム、「IROHATHM」をプレイするために2人でゲームセンターに来ました。 2人はただ遊んでも面白くないと思ったので、以下のゲームをして所持金を分配してから遊ぶことにしました。
- 箱 A,B,C を用意する。
- A に100円玉を A_1 枚、50円玉を A_2 枚入れる。
- B に100円玉を B_1 枚、50円玉を B_2 枚入れる。
- C に100円玉を C_1 枚、50円玉を C_2 枚入れる。
- 物理好きさんから始めて、「その時点でコインの入っている箱をどれか選び、選ばれた箱の中からランダムにコインを1枚取り出す」という動作をコインが全て取り出されるまで交互に行う。この時取り出したコインが100円玉と50円玉のどちらであるかは双方が知ることができる。
両者が最終的な所持金の期待値を最大化するようにこのゲームを行った場合、物理好きさんが最終的に所持している金額の期待値を求めてください。 ただし、100円玉と50円玉はとてもそっくりで、どちらを取り出す確率も同様に確からしいとします。
制約
- 入力はすべて整数
- 0 \leq A_1,A_2,B_1,B_2,C_1,C_2 \leq 10
- コインは全体で1枚以上存在する。
入力
A_1 \ \ A_2 B_1 \ \ B_2 C_1 \ \ C_2
出力
解を1行に出力してください。但し、誤差は絶対誤差または相対誤差で 10^{-9} まで許容されます。
入力例1
1 1 1 0 1 0
出力例1
175.000000000000
確実に100円もらえる箱が2つと100円、50円が一枚ずつ入った箱があります。 両者は一ターン目でそれぞれ確実に100円を得てから物理好きさんが箱 A からコインを一枚引くのが最善で、このとき物理好きさんが得る金額の期待値は175円となります。
入力例2
0 0 0 0 1 10
出力例2
327.272727272727
コインが入っている箱が1つしかないので、交互に箱 C の中から1枚ずつ引くしかありません。100円玉を引き当てる確率はどのタイミングでも \frac{1}{11} なので、物理好きさんは6回の手番の中で \frac{6}{11} の確率で100円玉を引き当てます。 よって期待値は \frac{6}{11} \times 350+\frac{5}{11} \times 300=\frac{3600}{11}となります。
入力例3
5 6 7 8 9 10
出力例3
1686.539074960127
解説
総入れ替え-解説Time Limit: 1 sec / Memory Limit: 256 MB
配点: 600 点
問題文
※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。
今日はきたむーとその彼女にとって待ちに待った「初めて一緒に花を摘んだ」記念日である。彼は今日、 K 本の花を彼女にプレゼントするはずだった。しかし、彼はあまりにも多い記念日を管理しきれず、花を買うのを忘れてしまった。そこで彼は通学途中に花を買っていくことにした。
きたむーが住む街には N 個の駅があり、各駅には 1～N の番号が振られている。また、彼が使用している鉄道には M 本の線路があり i 本目の線路は料金 C_i 円で2つの駅 A_i と B_i を結んでおり、相互に行き来することができる。駅 j では X_j 本の花のセットを Y_j 円で好きなだけ買うことができる。彼は駅 1 の周辺に住んでおり、彼の学校は駅 N の周辺にある。
さて、彼が必要な K 本以上の花を買った後に通学するのにかかる交通費と花の代金の合計の最小値はいくらだろうか？
制約
- 入力はすべて整数
- 2 \leq N \leq 1000
- 1 \leq M \leq 2000
- 1 \leq K \leq 1000
- 1 \leq A_i,B_i \leq N (1 \leq i \leq M)
- 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
- 0 \leq X_j \leq K (1 \leq j \leq N)
- 1 \leq Y_j \leq 10^9 (1 \leq j \leq N)
2019/05/01 21:32 追記: 制約において、一部 N が M 、 M が N となっている間違いがあったため修正しました。
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
きたむーが K 本以上の花を買った後に通学するのにかかる交通費と花の代金の合計の最小値を1行で出力せよ。ただし、花を K 本以上買うことができない場合や、学校に絶対にたどり着けない場合は-1を出力せよ。
入力例 1
4 3 10 1 2 100 2 3 100 3 4 100 3 10 5 20 10 1000 1 8
出力例 1
338
駅 1 から、駅 2 、駅 3 を経由して駅 4 へ移動する。交通費の合計は 300 円となる。駅 1 で 3 セット、駅 4 で 1 セット購入すれば、花の代金の合計は 38 円となる。
入力例 2
4 4 3 1 2 50 2 3 50 3 4 100 3 1 100 2 500 2 200 2 500 2 500
出力例 2
600
購入する花が K 本より多くなってもいいことに注意せよ。
入力例 3
2 1 1 1 2 1 0 1 0 1
出力例 3
-1
入力例 4
10 16 10 6 10 3 3 1 4 2 3 9 8 8 8 10 4 10 6 5 9 2 3 1 7 4 3 8 2 2 6 10 9 8 6 10 8 3 4 7 8 2 6 4 6 8 7 9 9 6 7 5 10 4 3 7 7 1 8 3 8 5 1 6 3 1 7 2 8 7 8
出力例 4
22
解説
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 700 点
問題文
時は42XX年、世界は高橋君の呼び出した様々な存在により崩壊しつつあった。あなた以外の賢人たちはいまやみな限りのない空虚に呑み込まれ、残されたあなたと、巫女であったアブドゥル・いろはザードの遺した魔導書のみが希望である。すでに時間は残されておらず、任意の事象はあなたの 0 だけ後ろに這い寄っている。研究の結果、高橋君の唱えた呪文は長さ N の整数列 B_1, B_2, \dots, B_N であり、世界を安穏に戻すには、次の条件を満たす長さ N の整数列 A_1, A_2,\dots,A_N を呪文として唱えればよいことがわかった。
- A_i は 1 以上 10^6 以下の整数である。
- 1 \leq i \leq N である整数 i について、次の条件を満たす最大の整数 0 \leq x < i は B_i である。
- A_1 から A_x までの x 要素を取ってきた数列と、A_{i-x+1} から A_i までの x 要素を取ってきた数列が、列として等しい。
条件を満たす数列 A_1, A_2,\dots,A_N があるかどうか判定し、あるならば 1 つ示せ。
制約
- 入力はすべて整数
- 1 \leq N \leq 10^5
- 0 \leq B_i < i
入力
入力は以下の形式で標準入力から与えられます。
N B_1 B_2 \cdots B_N
出力
1 行目には、条件を満たす数列があればYesを、なければNoを出力してください。
条件を満たす数列があれば、2 行目に一例を空白区切りで出力してください。
答えが複数存在する場合、どれを答えても構いません。
入力例 1
8 0 0 1 0 1 2 3 2
出力例 1
Yes 1 2 1 3 1 2 1 2
たとえば i=6 について考えると、
- A_1 から A_2 までの2要素を取ってきた列は (1, 2) 、 A_{6+1-2} から A_6 までの2要素を取ってきた列は (1, 2) なので、 x=2 のときに条件は満たされます。
- A_1 から A_4 までの4要素を取ってきた列は (1, 2, 1, 3) 、 A_{6+1-4} から A_6 までの2要素を取ってきた列は (1, 3, 1, 2) なので、 x=4 のときは条件は満たされません。
条件を満たす最大の整数は x=2 なので、B_6 = 2 に矛盾しません。
入力例 2
4 0 1 2 1
出力例 2
No
解説
解説Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 800 点
問題文
南極海は、H \times W のマス目で表されます。海の上から i マス目、左から j マス目の部分を (i, j) で表します。
南極海には多くの氷山があります。探検家のいろはちゃんは、(s_x, s_y) から (g_x, g_y) まで、上下左右に隣り合ったマス目への移動を繰り返して移動したいです。氷山があるマス目に移動することはできないので、いくつかの氷山を融かす必要があるかもしれません。
それぞれの氷山には融かすためのコストが決まっています。k 個目の氷山をすべて融かすためのコストは C_k 円です。 いろはちゃんが (s_x, s_y) から (g_x, g_y) にたどり着くための最小のコストは何円でしょうか？
氷山は X 個あります。マス (i, j) の状態は A_{i,j} です。 A_{i,j} = 0 のとき、このマスには氷山がないことを表します。 1 \leq A_{i,j} \leq X のとき、このマスには氷山 A_{i,j} があることを表します。 ただし、同じ番号がついた氷山のマスは上下左右に連結です。
制約
- 入力はすべて整数
- 1 \leq H, W \leq 500
- 1 \leq s_x, g_x \leq H (2019/05/01 13:45 追記)
- 1 \leq s_y, g_y \leq W (2019/05/01 13:45 追記)
- (s_x, s_y), (g_x, g_y) は両方とも氷山ではないマス
- 1 \leq X \leq HW - 2
- 0 \leq A_{i,j} \leq X
- A_{i,j} に 1, 2, 3, \dots, X がすべて含まれる
- 1 \leq C_i \leq 10^{10}
部分点
- H, W \leq 40, X \leq 9 を満たすテストケースすべてに正解すると、160 点が与えられる。
- H, W \leq 40 を満たすテストケースすべてに正解すると、さらに 400 点が与えられる。
- すべてのテストケースに正解すると、さらに240点が与えられる
入力
入力は以下の形式で標準入力から与えられます．
H W X
s_x s_y
g_x g_y
A_{1, 1} A_{1, 2}\ \cdots\ A_{1, W}
A_{2, 1} A_{2, 2}\ \cdots\ A_{2, W}
\vdots
A_{H, 1} A_{H, 2}\ \cdots\ A_{H, W}
C_1 C_2\ \cdots\ C_X
出力
いろはちゃんがスタートからゴールにたどり着くための最小コストを出力してください。
入力例 1
4 5 4 2 1 3 5 1 1 1 2 2 0 1 0 2 0 0 3 0 4 0 3 3 4 4 4 10 5 8 12
出力例 1
13
入力例 2
5 7 6 5 3 2 7 2 2 2 1 1 3 3 2 2 2 1 1 3 0 2 6 6 6 1 3 5 2 6 6 6 1 4 4 2 2 0 1 1 4 4 927 138 284 714 456 798
出力例 2
1211
解説
解説Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 900 点
問題文
青木さんは高橋君と遊ぶ約束をしていましたが、待てど暮らせど高橋君が来ないので、次のような遊びをすることにしました。
- N 枚の赤いカードと N-1 枚の青いカードを、一列に交互に並べておく。つまり、まず赤いカードを一列に並べ、隣り合う赤いカードの間に青いカードを置く。
- 左から i 番目の赤いカードには、はじめ非負整数 A_i が書いてある。
- 左から i 番目の青いカードには、片方の面に
+が、他方の面に×が書いてある。S_i が+のとき+の面が、S_i が*のとき×の面がはじめ表向きである。 - 青木さんは、Q 個のクエリを番号順に実行する。i 番目のクエリの内容は 3 つの非負整数 T_i, X_i, Y_i で表され、以下のように解釈する。
- T_i = 1 のとき、左から X_i 番目の赤いカードに書かれた整数を Y_i に書き換える。
- T_i = 2 のとき、左から X_i 番目の青いカードを裏返す。このクエリにおいては、Y_i = 0 が保証される。
- T_i = 3 のとき(回答クエリ)、左から X_i 番目の赤いカードを左端、Y_i 番目の赤いカードを右端とする部分カード列を数式として見て、その計算結果を答える。ただし、青木さんは紙やペンもなしに大きな数を計算できないので、10^9+7 で割った余りを答える。
いろはちゃんは、青木さんの答えが合っているか確認するために、上の遊びをシミュレートするプログラムを書くことにしました。
制約
- S は
+と*のみから成る長さ N-1 の文字列、その他はすべて整数 - 2 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 1 \leq Q \leq 10^5
- 各質問 T_i,\ X_i,\ Y_i について、以下の 3 つのいずれかが成り立つ
- T_i = 1,\ 1 \leq X_i \leq N,\ 0 \leq Y_i \leq 10^9
- T_i = 2,\ 1 \leq X_i \leq N - 1,\ Y_i = 0
- T_i = 3,\ 1 \leq X_i \leq Y_i \leq N
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \cdots A_N S Q T_1 X_1 Y_1 \vdots T_Q X_Q Y_Q
出力
各回答クエリの正しい答えをそれぞれ 1 行で順に出力してください。
入力例 1
5 1 2 3 4 100 **+* 5 3 1 4 1 5 5 3 4 5 2 1 0 3 1 5
出力例 1
10 20 27
1行目には、1\times2\times3+4=10を出力します。+や×は、通常の四則演算と同じように計算します。
入力例 2
30 141056031 626562406 398984580 302301632 724833823 819260147 433302050 210081 464012738 867417506 592634049 207581070 196502965 201049574 651294024 481261837 785858015 132486153 389688195 704728852 193622905 503147306 35766369 884292216 743597128 172030481 568485269 51112624 850324303 618492623 **+**++++*+***+*++******++*++ 30 3 8 9 2 21 0 1 18 32689954 2 27 0 2 28 0 3 5 23 3 3 3 1 19 705926811 3 19 21 2 8 0 2 20 0 3 8 25 2 2 0 1 23 249011956 3 4 17 2 2 0 2 2 0 3 15 23 3 1 16 2 2 0 3 20 28 3 17 21 1 25 300797469 2 14 0 3 6 30 3 4 28 2 10 0 1 5 102545023 1 30 895902786 3 1 30
出力例 2
464222819 10116361 398984580 494861147 781529391 919851764 726060889 72956646 887945392 641812930 620768060 243676249 751282029
解説
Time Limit: 3 sec / Memory Limit: 256 MB
配点: 1200 点
これはインタラクティブな問題である。
この問題は高速な言語で解答することを推奨する。C++14 (GCC 5.4.1) で AC できることが確認されている。
問題文
※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。
今日は夏休み。きたむーは愛する彼女と虫取りに来ている。実は虫取りは二人の愛を深める非常に有意義な共同作業なのだ！
きたむーは1本のりんごの木を見つけた。このりんごの木は 1 個の根、N-1 個の葉または節点、 N-1 本の枝からなり、情報科学で言うところの木構造と酷似している。葉または節点、および根のことを以下では頂点と呼ぶ。根には番号 0 が、各頂点には番号 1 \sim N-1 が振られている。はじめ、きたむーは根にいる。
このりんごの木からは美味しい果実が取れるので、頂点にはすぬけ虫がやってくる。すぬけ虫は群れで生活していて非常に賢く、ある頂点を根とした部分木の各頂点に分散して止まる。例えば頂点数 3 の部分木に 15 匹のすぬけ虫がやってきたとき、 5 匹ずつに分かれて各頂点に止まる。なお、すぬけ虫は群れの虫の数が頂点数で割り切れないような部分木にはやってこない。なお、最初各頂点に止まっているすぬけ虫は 0 匹である。
この木は非常に高くそびえており、虫取り網ではとても届かないので、きたむーは頂点間を移動してすぬけ虫を取ることにした。ただし、いちいち木を降りてすぬけ虫の居場所を確認していては時間が勿体ないので、彼女から Q 回指示を受けて、頂点間を移動することにした。
指示は以下の 2 種類からなる。
指示 A は
0 i k
という形で与えられる。これは、i 番目の頂点を根とする部分木に k 匹のすぬけ虫の群れがやってきたことを意味する。
指示 B は
1 i
という形で与えられる。このとき、きたむーは現在いる頂点から i 番目の頂点まで、最短経路で移動する。その際、始点・終点を含む移動中に通った頂点にいたすぬけ虫をすべて捕獲し、その総数を彼女に報告する。その後、きたむーは次の指示 B があるまで頂点 i にとどまる。
二人の愛を試す虫取りの試練が今始まる・・・。
制約
- 入力はすべて整数
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 8 \times 10^4
- 0 \leq C_j,D_j \leq N-1\ (1 \leq j \leq N-1)
- 入力されるグラフは木である
- 0 \leq i \leq N-1
- 0 \leq k \leq 10^{9}
- k は頂点 i を根とする部分木の頂点数で割り切れる
部分点
- 以下の入出力例に正解すると 1 点が得られる。
- すべてのテストケースに正解すると、さらに 1199 点が得られる。
入力
入力は以下の形式で標準入力から与えられる。
N Q
C_1 D_1
C_2 D_2
\vdots
C_{N-1} D_{N-1}
指示1
指示2
\vdots
指示Q
ここで、整数 C_i,\ D_i は、 N-1 本の枝のうち i 番目の枝は頂点 C_i と D_i を結んでいるという意味である。
出力
指示 B が与えられるごとに、捕まえたすぬけ虫の総数を報告せよ。
実装上の注意
- この問題は インタラクティブな問題 である。指示 B が与えられた後に捕まえたすぬけ虫の数を報告しない限り、次の指示が与えられないので注意せよ。
- 出力のあと、標準出力を flush しなければならない。 そうでないときは
TLEの可能性がある。 - 答えを出力した後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。
- 出力の答えが間違っている場合の挙動は定義されていない (
WAとは限らない)。
入力例 1
6 4 0 3 3 1 3 2 4 5 0 5 0 3 9 0 1 2 0 2 5 1 1
出力例 1
8
入力例 2
9 9 0 5 0 2 0 1 5 8 5 7 5 4 2 3 2 6 0 0 9 0 2 6 0 8 4 1 8 1 1 0 3 8 0 0 144 0 3 32 1 3
出力例 2
7 1 110
実際には指示 B のあとに解答を出力しないと次の指示が与えられないことに注意せよ。