AtCoder Beginner Contest 221 F問題 Diameter set

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 頂点の木 $T=(V,E)$ が与えられる. $T$ の直径を $\operatorname{diam}(T)$ とする. このとき, 以下の条件を満たす部分集合 $S \subset V$ の個数を求めよ.

$|S| \geq 2$
$\forall u,v \in S; u \neq v \Rightarrow \operatorname{dist}(u,v)=\operatorname{diam}(T)$ . ただし, $\operatorname{dist}(u,v)$ は $T$ における頂点 $u,v$ 間の距離

制約

$2 \leq N \leq 2 \times 10^5$

解法

$T$ において, $\operatorname{dist}(x,y)=\operatorname{diam}(T)$ となる2つの頂点 $x,y \in V$ を取ってくる. なお, この $x,y \in V$ は BFS を2回行うことで取ってくることができる. そして, $x,y$ パスを $P_{x,y}: x=p_0, p_1, \dots, p_{\operatorname{diam}(T)}=y$ とする.

$\operatorname{diam}(G)$ が偶数のとき

$k:=\operatorname{diam}(T)/2$ として, $a:=p_k$ とする. このとき, 任意の $v \in V$ に対して, $\operatorname{dist}(a,v) \leq k$ である. よって, $T$ を頂点 $a$ を根とする根付き木と見なす. すると, 頂点 $v \in V$ における深さを $\operatorname{dep}(v)$ , 頂点 $u,v \in V$ の最小共通先祖を $\operatorname{lca}(u,v)$ と書くことにすると,

$\operatorname{dist}(u,v)=\operatorname{diam}(T) \iff \operatorname{dep}(u)=\operatorname{dep}(v)=k, \operatorname{lca}(u,v)=a$

となる. 更に, $\operatorname{lca}(u,v)=a$ の部分を言い換える. 根 $a$ の子を $b_1, \cdots, b_l$ とする. このとき, $T$ の部分グラフで, $b_i$ を根とした部分木を $B_i$ とする. そして, $W_i$ を $B_i$ に属する頂点の集合とし, 根でない頂点 $v \in V$ に対して, $\operatorname{group}(v)$ で, $v \in W_i$ となる $i$ を表すとする. このとき,

$\operatorname{lca}(u,v)=a \iff \operatorname{group}(u) \neq \operatorname{group}(v)$

よって, 以下のような問題に帰着できる.

以下を満たすような $S \subset V$ はいくつか?

$|S| \geq 2$
$\forall v \in S; \operatorname{dep}(v)=k$
$\forall u,v \in S; u \neq v \Rightarrow \operatorname{group}(u) \neq \operatorname{group}(v)$

一旦, $|S| \geq 2$ という条件を考えないことにする. このとき, 各部分木から $S$ の要素に選ぶことができるのは高々 $1$ 頂点である. よって, $W_i$ のうち, 深さが $k$ であるような頂点の個数を $L_i$ とすると, 各 $W_i$ での選択はどれも要素にならないか, $L_i$ 個の頂点からどれか $1$ つ選ぶの合わせて $L_i+1$ 通りである. また, ある部分木での選択は他の部分木での選択には影響を与えないことから, 中段, 下段を満たす $S$ の選び方は

$\displaystyle{\prod_{i=1}^l (L_i+1)}$

通りである. このうち, $|S| \lt 2$ となってしまうのは, $|S|=0$ の場合と, $|S|=1$ の場合である.

$|S|=0$ となるのは, $S=\emptyset$ の場合に限り, これは $1$ 通りである.
$|S|=1$ となるのは, ある $\operatorname{dep}(v)=k$ となる $v \in V$ で, $S={v}$ となる場合である. $\operatorname{dep}(v)=k$ となる頂点の数は $L_1+\dots+L_l$ である.

よって, 求めるべき解答は,

$\displaystyle{\prod_{i=1}^l (L_i+1)-\left(1+\sum_{i=1}^l L_i \right)}$

である.

$\operatorname{diam}(G)$ が奇数のとき

$k:=(\operatorname{diam}(T)-1)/2, k':=(\operatorname{diam}(T)+1)/2$ として, $a:=p_k, b:=p_{k'}$ とする. このとき, 木 $T$ から辺 $e=ab$ を取り除いたグラフ $F:=T-e$ はちょうど 2 つの連結成分からなる森である. $F$ の 2 つの連結成分を $X,Y$ としたとき, 任意の $X$ に属する 2 つの頂点 $v,v'$ において, $\operatorname{dist}(v,v') \leq 2k \lt \operatorname{diam}(T)$ である. $Y$ 側も同様である.

よって, $|S| \geq 2$ という条件も合わせることで, 条件を満たすような $S \subset V$ は $X$ 側の $a$ からの距離が $k$ である頂点 $x$ と, $Y$ 側の $b$ からの距離が $k$ である頂点 $y$ で, $S=\{x,y\}$ と表さなれなければならない. 逆に, このように $S$ が表せるならば, 必ず $S$ は条件を満たす.