-
-
考えたこと
- 例えば
- クエリが一つだったら木の形によらず不可能
- クエリが二つの時、完全に重なってない限り不可能
- クエリが3つの時ab, bc, caならOK
- つまりサイクルになれば良さそう
- 複数個はアリ
- つまりクエリの端に出てくる回数を数えて偶数回ならOK
- 証明は？
- クエリが奇数回しか触れてない点の周辺にはからなず奇数の辺ができる
- 木であるので2点をつなぐパスは一意
- ab, bcがある時にabcをこの順でたどる経路のうちac上にないものは往復して2回通る
- 例えば
-
公式解説
- 方針OK
- 証明は根つき木にしてmod 2で考える
