競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 152F問題

ABC152F

解法

条件の否定を考えると，黒が 0箇所となるので，扱いやすい． よって包除原理が使いやすい． 共通部分を求める包除原理を用いる． この場合，\(s \in 2^{M}\) を動かすとき，\(s = \emptyset\) を含むことと， 符号 \*1 return true;

        eset[i] ^= 1LL << e.id;
      }
      return false;
    };
   
    dfs(dfs, a, -1);
  }

  ll ans = 0;
  rep(s,1LL << m){ // include s = 0
    ll sig = __builtin_parityll(s) ? -1 : 1;
    ll es = 0;
    rep(i,m) if(s >> i & 1){
      es |= eset[i];
    }

    ll x = 1LL << (n-1-__builtin_popcountll(es));
    ans += sig * x;
  }
  cout << ans << endl;

  return 0;
}

*1:-1)^{|s|}\) に注意． 和集合の包除原理とは異なる．
任意の \(s \in 2^{M}\) と 任意の \(i \in s\) に対して 条件 \(i\) を満たすことは， \( t := \cup_{i \in s} E(path_{a_{i},b_{i}})\) を白にする事と同値． よって，残り \(N-1 - |t|\) 本の辺を自由に選べることと同値なので， \(2^{N-1-|t|}\) 通り．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

struct Edge{
  ll to, id;
  Edge(){}
  Edge(ll to, ll id): to(to), id(id){}
};

int main() {
  ll n;
  cin >> n;
  vector<vector<Edge>> g(n);
  rep(i,n-1){
    ll a,b; cin >> a >> b;
    --a, --b;
    g[a].emplace_back(b,i);
    g[b].emplace_back(a,i);
  }

  ll m; cin >> m;
  vll eset(m);
  rep(i,m){
    ll a,b; cin >> a >> b;
    --a, --b;

    auto dfs = [&](auto dfs, ll cu, ll pa) -> bool {
      if(cu == b) return true;
     
      for(auto e: g[cu]) if(e.to != pa){
        eset[i] ^= 1LL << e.id; // 1LL << を忘れない
        if(dfs(dfs, e.to, cu