AtCoder Beginner Contest 368 : D : Minimum Steiner Tree

問題文

　https://atcoder.jp/contests/abc368/tasks/abc368_d

問題概要

　$n$ 頂点の木 $G = ( V, E )$ と $V$ の部分集合 $W$ が与えられる．$G$ の $W$ をターミナルとする最小 Steiner 木の頂点数を求めよ．

制約

• $1 \leq |W| \leq n \leq 2 \times 10^5$

解法

　求めるべき最小 Steiner 木を $T$ と書きます．Steiner 木の定義から $W$ の任意の 2 頂点 $u, v \in W$ は $T$ において連結です．これは $G$ が木であることから，$G$ における（唯一の）$u$-$v$ パスが $T$ に含まれていることと同値です．従って，頂点の集合であって任意の $u, v \in W$ について $G$ の $u$-$v$ パスを含むものの内で極小なものによって誘導されるグラフが $T$ です．
　$G$ の各頂点について $T$ に含まれるか否かはどうやって判定すればよいかという話になりますが，大まかに以下の 2 つの方針があると思います：

• $T$ に自明に含まれる頂点から始めて，必要な頂点を追加していく．
• $T$ に自明に含まれない頂点から始めて，不要な頂点を削除していく．

それぞれについて説明します．

方針 1

　$W$ の適当な頂点 $u \in W$ をとり，$G$ を $u$ を根とする根付き木と考えます．各頂点 $v \in V$ について，ある頂点 $w \in W$ であって $u$-$w$ パスに $v$ を含むようなものが存在するとき，$v$ は $T$ に含まれなければならず，そうでないなら $v$ を $T$ に含むと極小ではなくなることで最小 Steiner 木ではなくなってしまうので $T$ に含められません．この条件は

• $v$ を根とする部分木に $W$ の元を含むなら $v$ は $T$ に含まれる

と言い換えられます．
　よって，$u$ を始点とする DFS を行うなどして条件を満たす部分木の個数を計算すれば答えが求まります．
　この解法は $G$ の各頂点・各辺を定数回ずつ参照するので，$\Theta( n )$ 時間で動作します．

方針 2

　ある頂点 $u \in V$ が以下の条件を共に満たすとします：

• $u$ は $G$ の葉である．
• $u \not \in W$ である．

これらを併せると，$u$ は「$T$ に含まれなければならないパス」には含まれないことが分かります．よって $u$ を $G$ から削除できます．
　これを可能な限り繰り返し適用すると葉がすべて $W$ の元であるような木が残ります．このとき，葉は削除できませんし，葉以外を削除すると連結ではなくなるのでこちらも削除できません．よって，この残ったグラフが $T$ です．
　この処理は，次数 $1$ の頂点をキュー（など）に入れて「将来削る頂点」を管理しつつ，各頂点の現在の次数を管理・更新して $1$ になったらキューに入れるようにすれば実装できます．
　この解法も各頂点・各辺を定数回ずつ参照するので $\Theta( n )$ 時間で動作します．

コード

void dfs( const VVI &G, VI &is_target, const int u, const int p = -1 )
{
	FOR( v, G[u] )
	{
		if ( v == p )
		{
			continue;
		}

		dfs( G, is_target, v, u );
		is_target[u] |= is_target[v];
	}

	return;
}

int main()
{
	IN( int, N, K );
	VVI G( N );
	REP( N - 1 )
	{
		IN( int, u, v );
		--u, --v;
		G[u].PB( v );
		G[v].PB( u );
	}
	VI V( K );
	cin >> V;
	MAP_PRED( V );

	VI is_target( N );
	for_each( ALL( V ), [&]( const int v ){ is_target[v] = true; } );

	dfs( G, is_target, V[0] );

	cout << accumulate( ALL( is_target ), 0 ) << endl;

	return 0;
}

int main()
{
	IN( int, N, K );
	VVI G( N );
	REP( N - 1 )
	{
		IN( int, u, v );
		--u, --v;
		G[u].PB( v );
		G[v].PB( u );
	}
	VI V( K );
	cin >> V;
	MAP_PRED( V );

	VI is_target( N );
	for_each( ALL( V ), [&]( const int v ){ is_target[v] = true; } );

	VI degrees( N );
	REP( u, N )
	{
		degrees[u] = SZ( G[u] );
	}

	queue< int > que;
	REP( u, N )
	{
		if ( !is_target[u] && degrees[u] == 1 )
		{
			que.push( u );
		}
	}

	int res = N;
	VI processed( N );
	while ( !que.empty() )
	{
		const int u = que.front();
		que.pop();

		processed[u] = true;
		--res;

		FOR( v, G[u] )
		{
			if ( !processed[v] && !is_target[v] && --degrees[v] == 1 )
			{
				que.push( v );
			}
		}
	}

	cout << res << endl;

	return 0;
}