ABC287 F問題 Components

木の特徴

木＝連結で閉路を持たない(無向)グラフ

n 個の点からなる木は、 $n − 1$ 本の辺を持ちます。

誘導部分グラフ＝グラフから一部の頂点を取り出し、その頂点間の辺の有無は元のグラフと全て同じグラフ

木の誘導部分グラフは、閉路を持ちませんが、連結ではなく複数の連結成分を持つ可能性があります。
ひとつひとつの連結成分について、その頂点の数より 1 少ない辺を持ちます。

そのため、グラフに含まれる頂点の数から辺の数を引いた値が連結成分の数と同じになります。

動的計画法 - 枝分かれのないグラフの場合

枝別れのないグラフ (各頂点の次数がすべて 2以下) を考えます。
このグラフの端から $i$ 個の頂点だけに限った誘導部分グラフ (すべて選ばないケースも含めて $2^i$ 種類) のうち、頂点の数から辺の数を引いた値が $j$ である部分グラフの個数を仮に $dp_{i,j}$ と表すことにします。これに端から $i+1$ 番目の頂点を追加すると、

$i$ 番目の頂点を含まない部分グラフでは、 $i+1$ 番目の頂点を含むと頂点の数が1増える。
$i$ 番目の頂点を含む部分グラフでは、 $i+1$ 番目の頂点を含むと頂点の数と辺の数が1つずつ増えるので、頂点と辺の数の差は変わらない。
$i+1$ 番目の頂点を含めない場合、頂点・辺の数は変わらない。

ということになります。
そのため、追加する $i+1$ 番目の頂点の一つ前の $i$ 番目の頂点を選んでいるか/選んでいないかを分けておく必要があります。
動的計画法の $dp_{i,j,k}$ を、端から $i$ 番目の頂点までについて、頂点と辺の数の差が $j$ でかつ最後の頂点を選んでいる or 選んでいない( $k=$ 1 or 0) で分けたときの部分グラフの数とします。
$dp$ を計算する式は、次のようになります。
$dp_{i+1,j,1}=dp_{i,j,1}+dp_{i,j-1,0}$
$dp_{i+1,j,0}=dp_{i,j,1}+dp_{i,j,0}$

動的計画法 - グラフの枝分かれ部分

次数が3以上の頂点を考えます。この場合、一つの端から計算を進めるだけでなく、複数の端の頂点から計算を進めて、途中で合流させる必要があります。
一つの端から $i$ 番の頂点まで計算したものを $dp_{i,ja,k}$ , 別の端から $i$ 番の頂点の一つ前の頂点まで計算したものを $dp_{i-1,jb,k}$ とします。
これらを合流する場合、 $i$ 番の頂点を選ぶケースについてはその頂点はすでにカウント済みであることを考える必要があります。頂点 $i , i-1$ を両方選ぶグラフでは辺の数が 1増えるので頂点と辺の数の差は、２つの dp の和より 1 小さくなります。
$dp_{i,ja,1}$ と $dp_{i-1,jb,0}$ の組み合わせからは、頂点と辺の数の差は合わせて $ja+jb$ で、対応する部分グラフの数は $dp_{i,ja,1}\times dp_{i-1,jb,0}$ となります。
$dp_{i,ja,1}$ と $dp_{i-1,jb,1}$ の組み合わせからは、頂点と辺の数の差は合わせて $ja+jb-1$ で、対応する部分グラフの数は $dp_{i,ja,1}\times dp_{i-1,jb,1}$ となります。
$dp_{i,ja,0}$ と $dp_{i-1,jb,*}$ の組み合わせからは、頂点と辺の数の差は合わせて $ja+jb$ で、対応する部分グラフの数は $dp_{i,ja,1}\times (dp_{i-1,jb,1}+dp_{i-1,jb,0})$ となります。

再帰関数を使った実装

複数の端から計算を進めるために、木構造の深さ優先探索の帰りがけ順で計算していって、根ノードや次数が3以上の頂点で合流していきます。

コード例 (Julia)
(Julia の配列は 1始まりなので、インデックスは +1 加算)

# 深さ優先探索
function DFS( prev, current, edge )

  MOD_ = 998244353

  n = length(edge[current])
  if n == 1 && prev > 0
    # 端の頂点 (葉)
    dp =  zeros(Int,2,2)
    dp[1,1] = 1  # dp_0,0
    dp[2,2] = 1  # dp_1,1
    return dp
  end

  first = 1

  for i = 1:n  # n:頂点の次数

    next = edge[current][i]

    if next == prev
      continue
    end

    dp1 = DFS( current, next, edge )
    n1 = size(dp1,1)

    if first == 1
      first = 0
      dp =  zeros(Int,n1+1,2)
      for j = 1: n1
        dp[j,2] += dp1[j,2]      # 両方の頂点を含んでいる場合
        if j > 1
          dp[j,2] += dp1[j-1,1]  # 追加の頂点の方だけ含んでいる場合 (+1)
        end
        dp[j,2] %= MOD_
        dp[j,1] = dp1[j,2] + dp1[j,1] # 追加の頂点を含まない場合
        dp[j,1] %= MOD_
      end
    else
      # 枝分かれの合流
      dp2 = dp
      n2 = size(dp2,1)
      dp = zeros(Int,n1+n2,2)
      for j = 1: n1
        for k = 1: n2
          dp[j+k-1,2] += dp2[k,2] * dp1[j,1]  # 追加の頂点の方だけ含んでいる場合 (+0)
          dp[j+k-1,2] %= MOD_
          if j+k > 2
            dp[j+k-2,2] += dp2[k,2] * dp1[j,2]  # 両方の頂点を含んでいる場合 (-1)
            dp[j+k-2,2] %= MOD_
          end
          dp[j+k-1,1] += dp2[k,1] * (dp1[j,2] + dp1[j,1] ) # 追加の頂点を含まない場合
          dp[j+k-1,1] %= MOD_
        end
      end
    end
  end

  return dp

end

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())


  # 入力データ
  N = readInt()

  # N=1 の場合、すぐ終了
  if N==1
    println(1)
    return
  end

  edge = [Vector{Int}() for _ = 1:N]

  for i = 1:N-1
    a, b = readInts()
    push!(edge[a], b)
    push!(edge[b], a)
  end

  # 深さ優先探索
  start = 1
  dp = DFS( -1, start, edge )

  n1 = size(dp,1)

  MOD_ = 998244353

  for i = 1:N
    if i+1 <= n1
      println( (dp[i+1,2]+dp[i+1,1])%MOD_ )
    else
      println( 0 )
    end
  end

end  # function solve


# main
solve()