木と計算量 後編 〜全方位木DP〜

前編はこちら

前編は汎用性も高い話題でしたが、後半は少しマニアックで雑学的です。

予習

全方位木DPについて予習します。

補足として、以下の問題を解く具体的な実装も置いておきます。

N 頂点の木が与えられる。
頂点 v を含む部分木の個数を全ての v について求めよ。
制約:1 ≦ N ≦ 10^6

こういう、根を全部試して根付き木の問題を一括で計算する、的な状況で全方位木DPが活躍します。

pythonで実装するとこんな感じになります。

def dfs(v, p=-1):
  deg[v] = len(to[v])
  res = 1
  dp[v] = [0]*deg[v]
  for i in range(deg[v]):
    u = to[v][i]
    if u == p:
      pi[v] = i
      continue
    dp[v][i] = dfs(u, v)
    res *= dp[v][i]+1
    res %= mod
  return res

def bfs(v, res_p=0, p=-1):
  if p != -1:
    dp[v][pi[v]] = res_p
  dpl = [1]*(deg[v]+1)
  for i in range(deg[v]):
    dpl[i+1] = dpl[i]*(dp[v][i]+1)%mod
  dpr = [1]*(deg[v]+1)
  for i in range(deg[v]-1,-1,-1):
    dpr[i] = dpr[i+1]*(dp[v][i]+1)%mod
  ans[v] = dpr[0]
  for i in range(deg[v]):
    u = to[v][i]
    if u == p:
      continue
    bfs(u, dpl[i]*dpr[i+1]%mod, v)

dfs(0)
bfs(0)

本編

本編と言いつつも、こちらは雑談みたいなものです。

全方位木DPには色んな流派があるみたいですね。
その中で、zerokugiさんの方法が計算量の視点から興味深かったので紹介します。

追記

僕のオススメは上に書いた方法です。(定数倍、実装量、ロジックの簡潔さなどの点から)
あと、zerokugiさんの方法っぽくやる場合でも次数の降順より行きがけ順の方が定数倍が良いです。

さっきの問題をzerokugi法で実装すると以下のようになります。

def dfs(v, p=-1):
  res = 1
  for i in range(deg[v]):
    u = to[v][i]
    if u == p:
      pi[v] = i
      continue
    if dp[v][i] is None:
      dp[v][i] = dfs(u, v)
    res *= dp[v][i]+1
    res %= mod
  return res

roots = []
for v in range(N):
  deg[v] = len(to[v])
  dp[v] = [None]*deg[v]
  roots.append([deg[v], v])
roots.sort()
roots.reverse()
for _, v in roots:
  ans[v] = dfs(v)
  dpl = [1]*(deg[v]+1)
  for i in range(deg[v]):
    dpl[i+1] = dpl[i]*(dp[v][i]+1)%mod
  dpr = [1]*(deg[v]+1)
  for i in range(deg[v]-1,-1,-1):
    dpr[i] = dpr[i+1]*(dp[v][i]+1)%mod
  for i in range(deg[v]):
    u = to[v][i]
    dp[u][pi[v]] = dpl[i]*dpr[i+1]%mod
print(ans)

実はこのアルゴリズムの計算量は O(N) なのです。

丁寧に書くと長くなるので、以下に示す本質部分だけを解析します。

  • dfs内のfor i in range(deg[v]):

dfs(v)を呼ぶ度にO(deg[v])がかかるという訳です。

根として呼ばれるのは各 v について1回ずつなので O(N) です。(Σ(deg[v]) =辺の本数*2)
問題はdfs内から呼ばれる場合です。

dfs(v)がdfs(u)内から呼ばれるのは、各辺 u-v について高々1回です。(結果がメモされるため)
で、実際に呼ばれる条件は以下の通りです。

  • u 側の部分木内に次数が deg[v] 以上の頂点がある

別の言葉で言うと「v より先に根としてdfsを呼ばれる頂点が u 側の部分木内に存在する」です。

つまり、以下のことが言えれば計算量が O(N) であることが示せます。

頂点数 N のどんな木についても、Σ(「vを取り除いてできる部分木のうち、次数がdeg[v]以上の頂点が含まれるものの個数」* deg[v]) が O(N) である。

適当な頂点を根とした根付き木だとみなします。上記の式は以下のように言い換えられます。

Σ(「vの下に付く部分木のうち、次数がdeg[v]以上の頂点が含まれるものの個数」*「vの子の個数」)

実際には根方向の辺も考えないといけないので「vの下〜個数」には +1 が付くこともありますし、「vの子の個数」にも +1 は付きますが、Σ(deg[v]) が O(N) であることを思い出すと、この部分につく定数は無視できることが言えます。

さて、これの最大値の抑え方が分からなかったのでtwitterで助けを求めると、hosさんからエレガントな解答をいただいたので紹介します。(WA_TLEさんもありがとうございます)

頂点数 N 最大次数 K の根付き木についての最大値を f(N,K) とおくと、f(N,K) ≦ N-1-K。

これで、下に示すような帰納法が回るようになります。("次数"に親方向の辺は数えないものとします)
自分も帰納法が回せたら良いなぁとは思っていましたが、この式には辿り着けませんでした。すごい。

とりあえず、f(1,0) = 0
根の次数を d とすると、各 d に対して以下が成り立つ。
f(N,K) \leq max(\sum (f(n_i,k_i)+min(k_i,d))\ | \sum n_i = N-1,\ k_i \lt n_i,\ k_i \leq K)
右辺のmaxの中身の f を外すと、
\sum n_i - d - \sum k_i + \sum min(k_i,d) = (N - 1) - d - \sum max(k_i-d,0)
d = K の場合:そのまま N - 1 - K 以下だと言える。
d < K の場合:k_i のいずれかは K なため d + \sum max(k_i-d,0) \geq K であり、やはり N - 1 - K 以下だと言える。

min(k_i,d) の部分が少しテクニカルですが、k_i と d の大小で場合分けしてみると正しいことが確認できるかと思います。

あとがき

次数の降順でやれば計算量が O(N) で抑えられるってかなり奇妙で面白い!

木は奥深いですね。

おまけ

全方位木DPについて、普通のDPの場合はこれで良いのですが、データ構造で高速化するDPの場合などはまた別のアプローチをする必要があったりします。(前にHackerRankで使って以来、使う問題とは出会ってないけど。これの記事需要あります?)