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

問題分割
木の辺ラベルの更新
辺ラベルを更新しなくても端点だけ見れば良い

Related Pages

  • →問題分割×バイナリ素性×abc172e×包除原理_解ける数え上げの範囲を広げよう×部分集合の部分集合の数の和×高速メビウス変換×二項係数×メビウス変換×完全順列×オイラー標数→
  • 包除原理
  • →僕のatcoderの学び方(〜水色)×僕のatcoderの学び方(〜past上級)×abc187×past過去問練習202012×変形テクニックに名前をつける×頂点数18の制約×辺が10^5の制約×行列の半分×二項定理×足し算の順序の変更×辺が10^5ならダイクストラ使える×典型力×問題変換×問題分割×認知の解像度×概念のハンドル×atcoder失敗リスト×atcoderentrypoint×アルゴリズム実技検定×第五回_アルゴリズム実技検定×最小費用流に帰着×帰着訓練→
  • 僕のatcoderの学び方(〜青)
  • →2回やっても意味がない×問題分割×数列の昇順並び替え×操作回数の最小化×agc024→
  • AGC024B
  • →帰着する力×agc022c×ゴールから逆算×2回やっても意味がない×最適な操作の順番が一位×コストが2^k→辞書順最小×1〜xで足りて1〜x-1で足りない時xは必須×問題変換×問題分割×状態情報の圧縮→
  • 典型力
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]