E - Virus Tree 2 「根っこは特別」

Quiz

https://atcoder.jp/contests/abc133/tasks/abc133_e

解説

• snukeさんの解説放送 https://www.youtube.com/watch?v=8uowVvQ_-Mo

ひとこと

void dfs(int v, int p=-1) {
  for (int u : to[v]) {
    if (u == p) continue;
    dfs(u,v);
  }
  int nk = (p==-1) ? k : k-2;  // n
  int c = (p==-1) ? to[v].size()+1 : to[v].size()-1; // r
  ans *= f(nk,c); // nCr
}

• 解説放送でハッとしたのはこの箇所
• dfsで塗っていく際に、根の場合は「自分＋自分の子」の塗り方を決め、子の場合は「自分の子」の塗り方を決める、というコードになっている

木を塗る際に考えたいこと

• dfs
• 葉から塗る
• 根から塗る
• nCr
• 塗り方に自分自身や親を含めるかどうかの、±1の調整（自分から伸びている手の数をnとしたとき、自分を含めるなら＋１だし、自分を含まないだとnそのままだし、自分を含まず親も含まないなら－１）

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～