LoginSignup
1

More than 3 years have passed since last update.

AtCoder Beginner Contest 138 D - Ki のテストケースがコンテスト後に増えている件について

Last updated at Posted at 2019-08-18

AtCoder Beginner Contest 138 D - Ki のテストケースがコンテスト後に増えている件について

追記: 1≤ai<bi≤N の条件があるので、以下の想像は誤りです!!
追々記: AtCoder Beginner Contest 138 D - Ki のテストケースがコンテスト後に増えている件について (修正版) - Qiita をご覧ください

AtCoder Beginner Contest 138 の終了後も D 問題を解説を見て試行錯誤していたら、AC だったコードが WA になって、after_contest_15, after_contest_16, after_contest_17 が増えていることに気づいた. 解説 PDF にも修正が入っていた.

問題文には 「この木の根は頂点 1 で、i 番目の辺 (1≤i≤N−1) は頂点 ai と頂点 bi を結びます。」とだけ書かれていて、頂点 ai と頂点 bi のどちらが根に近いかは不明なのだが、テストケースが追加される前は頂点 ai のほうが根に近いという決めつけをしていても通るテストケースになっていたと思われます. 追加されたテストケースはこの決めつけをしていると通らないように思われます. (だから解説 PDF に「根に近い頂点から順に行えば」という追記が入ったと思われる).

なので、追加されたテストケースの入力例としては、「入力例 1」の4行目をひっくり返した以下で行えそうである.

4 3
1 2
2 3
4 2
2 10
1 100
3 1

出力例は、「出力例 1」と同じ

100 110 111 110

となる.

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1