ツリーの独立セット:TreeDP

質問する

2213号:ツリーの独立集合

概要

これは、ツリーの最大独立セットを求め、その構成ノードを出力する必要があるという問題です.
この場合、最大独立セットは、独立セットの構成要素がグラフィックに隣接せず、要素の重みの和が最大である必要があります.

ツリーの独立セット

問題を解く

アクセスと時間の複雑さの計算

この問題はどのような方法で処理すべきですか.
まず、すべてのノードを最大独立セット(1)に含めることも、(2)を含まないこともできます.
すなわち,すべてのノードが2つの場合の数を共有する.
最もNaiveの解はO(2 N)O(2^N)O(2 N)の解が考えられる.NNNが大きいので当然タイムアウトです.)
この場合,時間的複雑さを低減する方向を考慮すべきである.
そう考えると、1≦N≦100001≦N≦100001≦N≦10000なので、O(Nlogn)O(Nlogn)O(Nlogn)、O(N)O(N)O(N)の時間的複雑さが一般的に考えられる.
O(Nlogn)O(Nlogn)O(Nlogn)O(Nlogn)には、ソート、二分検索、ソート、累積、データセグメントツリー化などがある.しかし,これはすべての状況を考慮した問題であるため,O(Nlogn)O(Nlogn)O(Nlogn)プールは一時的に保持できる.
では早速O(N)O(N)O(N)O(N)
ルートノードからリーフノードまで、上から下まで演算して問題を解決する必要があります.

せんたくアルゴリズム

この問題のNaive Han Paulをもう一度整理しましょう.
これはすべての状況の数を考慮してその中から最値を選択する必要があるという問題であるため,以前に用いた記録を用いたアルゴリズムを考えることができる.
選択可能なアルゴリズムはMemoization/DPである.また,この問題の解答はツリーの場合のDPと考えられる.

問題の簡略化

では、DPの属性を考えてみましょう.

一部の頂点は、自分の子供や両親と集合できない.

のすべての頂点において、集合Sを実現するための数は以下の通りである.

自己

を含む

自分を含まない

したがって、DPの属性は、以下のように定義することができる.

Dp[i][0]Dp[i][0]Dp[i][0]=iをルートノードとするサブツリーにiが含まれていない場合、ツリー内の独立セットの最大値
dp[i][1]dp[i][1]dp[i][1]=iをルートノードとするサブツリーにiを含む場合、ツリー内の独立セットの最大値は

となる.

自分が含まれている場合、必ずしもサブノードが含まれているとは限らない.

自分を含まない場合は、両方の場合で最高価格を選択します.

は、次のノードを含む:

次ノードを除く場合は

である.
ツリーの場合のDPは、通常、ツリーDPと呼ばれる.
ツリーDPでは、リーフノードの状況を知ることが重要である.
この問題では、リーフノードの場合は次のようになります.

リーフノードの状況:[1],[0]を含まないまたは含まない
リフノルドの場合は図のようです.また、それぞれの場合、dp[leaf][j]dp[leaf][j]dp[leaf][j]はリーフノードの重みに等しい.
次に、リーフノードではなくノードの場合を見てみましょう.

ic=ii c=iic=iノードのサブノード
Dp[i]Dp[i]Dp[i]では、次のようになります.これはすでに上記の内容です.

自分が含まれている場合、必ずしもサブノードが含まれているとは限らない.
自分が含まれている場合は、サブノードが含まれているとは限りません.

自分を含まない場合は、両方の場合で最高価格を選択します.

サブノードを含む場合は

である.

サブノードが含まれていない場合、

その時にその点を考えて、少し修正すると

自分が含まれている場合、必ずしもサブノードが含まれているとは限らない.
最大独立セット値は

で、サブノードがルートノードであるサブツリーにはサブノードが含まれません.

自分を含まない場合は、両方の場合で最高価格を選択します.
最大独立セット値

で、サブノードがルートノードであるサブツリーにサブノードが含まれます.

整理するなら.

各ノードの場合数をそのノードのサブノードと組み合わせて考える.

サブノードの最大値は、親ノードの最大値に影響します.(DPの概念)

親ノードで

子ノードを使用する場合の最大値.

逆トレースDPパス

では、どのようにして重み付けとパスを実現しますか?
既に作成したDP Tableを利用すればよい
経路は1番ノード(木のルートノード)から最大(Dp[i][0],Dp[i][1])max(Dp[i][0],Dp[i][1])max(Dp[i][0],Dp[i][1])を求める.
max(Dp[i][0],Dp[i][1])=Dp[i][0]max(Dp[i][0],Dp[i][1])=Dp[i][0]max(Dp[i][0],Dp[i][1])=Dp[i][0]であれば、このノードを含まないのが最大値となる.
max(Dp[i][0],Dp[i][1])=Dp[i][1]max(Dp[i][0],Dp[i][1])=Dp[i][1]max(Dp[i][0],Dp[i][1])=Dp[i][1]であれば、そのノードを含む場合が最大値となる.
パスを探すときには、以下の状況と作成したDPテーブルを用いて逆方向追跡を行うこともできます.

自分が含まれている場合、必ずしもサブノードが含まれているとは限らない.
最大独立セット値は

で、サブノードがルートノードであるサブツリーにはサブノードが含まれません.

自分を含まない場合は、両方の場合で最高価格を選択します.
最大独立セット値

で、サブノードがルートノードであるサブツリーにサブノードが含まれます.

インプリメンテーション

import sys

sys.setrecursionlimit(10 ** 6)
In = lambda: sys.stdin.readline().rstrip()

def init():
	nodes = int(In())
	vals = list(map(int, In().split()))  # 가중치
	vals.insert(0, 0)  # dummy value
	tree = []
	check = [0] * (nodes + 1)
	dp = [[-1, -1] for i in range(nodes + 1)]
	for i in range(nodes - 1):
		nodeX, nodeY = list(map(int, In().split()))
		tree[nodeX].append(nodeY)
		tree[nodeY].append(nodeX)
	return tree, dp, vals

def dynamicProgramming(cur, prev):
	dp[cur][1] = vals[cur]
	dp[cur][0] = 0
	for nextnode in tree[cur]:  # 자식노드 탐색, # 리프노드의 경우 for문 X
		if nextnode != prev:
			dynamicProgramming(nextnode, cur)
			dp[cur][1] += dp[nextnode][0]
			dp[cur][0] += max(dp[nextnode][0], dp[nextnode][1])

def findRoute(cur, prev, isVisited):
	if isVisited:
		answr.append(cur)
		for nextnode in tree[cur]:
			if nextnode != prev:
				findRoute(nextnode, cur, 0)  # 현재 노드를 포함 -> 자식 노드 포함 X
	else:
		for nextnode in tree[cur]:
			if nextnode != prev:
				if dp[nextnode][0] > dp[nextnode][1]:
					findRoute(nextnode, cur, 0)  # 현재 노드 포함 X-> 자식노드 포함 X
				else:
					findRoute(nextnode, cur, 1)  # 현재 노드 포함 X -> 자식노드 포함 O

if __name__ == "__main__":
	tree, dp, vals = init()
	dynamicProgramming(1, -1)

	answr = []
	if dp[1][0] > dp[1][1]:
		findRoute(1, -1, 0)
	else:
		findRoute(1, -1, 1)

	answr.sort()
	print(dp[1][0] if dp[1][0] > dp[1][1] else dp[1][1])
	print(*answr)