Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

となる.

c-yan
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした