公式
D - Minimum Steiner Tree 解説
by
条件を満たす木に悪い頂点が存在した場合、その頂点を削除しても条件を満たす木であるままです。よって頂点数最小の条件を満たす木には悪い頂点は存在しません。
2. 悪い頂点を持たない条件を満たす木⇒頂点数最小の条件を満たす木
悪い頂点を持たない条件を満たす木を任意にとり $T$、頂点数最小の条件を満たす木を任意に取り $T'$ とします。
一般に、木からその部分グラフである木を $2$ つとったとき、その共通部分は木または空となります。そこで、$T$ から $T\cap T'$ の頂点を縮約してできる木 $T''$ を考えます。
もし $T''$ の頂点数が $2$ 以上なら $T''$ は次数 $1$ の頂点を $2$ つ以上持ち、$V_1,\ldots,V_K$ は全て縮約されているので、次数 $1$ の頂点のうち少なくとも $1$ つは $T$ において悪い頂点となり仮定に反します。
よって $T''$ は頂点数 $1$ 、すなわち $T\subset T'$ となり、$T'$ の最小性から $T=T'$ となります。
以上で示せました。
D - Minimum Steiner Tree 解説
by 
kyopro_friends
\(K=1\) のとき答えは明らかに \(1\) です。そうでないときを考えます。
「もとのグラフからいくつかの(0 個でもよい)辺と頂点を削除してできる木のうち、頂点 V1,…,VK を全て含むようなもの」を条件を満たす木と呼ぶことにします。
「次数が \(1\) であり、\(V_1,\ldots,V_K\) のいずれでもない頂点」を悪い頂点と呼ぶことにします。
もとの木から始めて、悪い頂点とそれに接続する辺を削除することを可能な限り繰り返してできる木が求める木です。
証明
1. 頂点数最小の条件を満たす最小の木⇒悪い頂点を持たない条件を満たす木に悪い頂点が存在した場合、その頂点を削除しても条件を満たす木であるままです。よって頂点数最小の条件を満たす木には悪い頂点は存在しません。
2. 悪い頂点を持たない条件を満たす木⇒頂点数最小の条件を満たす木
悪い頂点を持たない条件を満たす木を任意にとり $T$、頂点数最小の条件を満たす木を任意に取り $T'$ とします。
一般に、木からその部分グラフである木を $2$ つとったとき、その共通部分は木または空となります。そこで、$T$ から $T\cap T'$ の頂点を縮約してできる木 $T''$ を考えます。
もし $T''$ の頂点数が $2$ 以上なら $T''$ は次数 $1$ の頂点を $2$ つ以上持ち、$V_1,\ldots,V_K$ は全て縮約されているので、次数 $1$ の頂点のうち少なくとも $1$ つは $T$ において悪い頂点となり仮定に反します。
よって $T''$ は頂点数 $1$ 、すなわち $T\subset T'$ となり、$T'$ の最小性から $T=T'$ となります。
以上で示せました。
この操作は、各頂点について、直接辺でつながっている頂点をsetで管理することなどで高速に行うことができます。
writer解(Python)
N,K = map(int,input().split())
edge = [set() for _ in range(N)]
for _ in range(N-1):
a,b = map(int,input().split())
a-=1
b-=1
edge[a].add(b)
edge[b].add(a)
V = set(map(int,input().split()))
V = set(x-1 for x in V)
deg = [len(s) for s in edge]
q = [i for i,d in enumerate(deg) if d==1]
ans = N
for v in q:
if v in V: continue
vv = edge[v].pop()
edge[vv].discard(v)
ans-=1
if len(edge[vv])==1: q.append(vv)
print(ans)
投稿日時:
最終更新: