問題概要
正整数 $n, k$ と $nk$ 頂点の木グラフ $G = ( V, E )$ が与えられる．$G$ を互いに共通部分をもたない長さ $k$ のパス（パスの長さは含まれる頂点数で定義）に分解できるか？（厳密な問題定義は原文参照）
制約
- $1 \leq n, k$
- $nk \leq 2 \times 10^5$
解法
$V$ の適当な要素を根と見做して根付き木として考えます．葉は必ずパスの端点になるので，（根を除く）葉から根方向へパスを伸ばしていく気持ちになってみます．
パスへの分解が可能であると仮定すると，ある部分木の根 $r$ に対してそれを含むパスがちょうど $1$ つ存在することになりますが，そのパスでの $r$ の役割は，
- 子孫方向から伸びてくる $1$ つのパスにくっついて，子孫側に伸びるパスを作る
- 祖先側のパスの長さが $0$（i.e., 伸びてくるパスの長さが $k - 1$ で，$r$ をくっつけると長さ $k$ のパスが完成する）場合を含む
- 子孫方向から伸びてくる $2$ つのパスを中継し長さ $k$ のパスを作る
の $2$ 通りになります．このことを踏まえて，$r$ の各子を（根側の）端点とする（長さ $k$ 未満の）パスの個数と長さに着目して場合分けをすると，
- 個数が $0$ : $k = 1$ なら長さ $1$ のパスを構成でき，そうでなければ根方向に接続するパスの端点になる
- i.e., $r$ 以下を長さ $k$ のパスに分解可能
- 個数が $1$ : その長さ $s$ が $k - 1$ なら $r$ を端点とする長さ $k$ のパスを構成でき，そうでなければ根方向へ伸びる長さ $s + 1$ のパスとなる
- 個数が $2$ : その長さの和 $s$ が $k - 1$ なら $r$ で中継することで長さ $k$ のパスを構成でき，そうでなければ不適
- それ以外 : $3$ 本以上の（長さ $k$ 未満の）パスをひとつの頂点ではまとめられないので不適
となります．各部分木の根 $r$ がどうなるかは葉からボトムアップに決まるので，深さ優先探索 (Depth-First Search; DFS) をして，
- $r$ は不適
- $r$ 以下を長さ $k$ のパスに分解可能
- $r$ を根側の端点とする長さ $s$ のパスができる
の（互いに背反な）状態のどれになるかを決定できます．よって（場合分けに気をつけて実装してから）DFS して，根の状態を見ることで問題に回答できます．
状態をどのような値で表現するかはやや悩みどころですが，不適を -1，分解可能を 0，それ以外は $r$ を端点とするパスの長さ自体で表すというのは割と素朴な気がします．
計算量についてですが，一回の DFS 中で各辺・各頂点をそれぞれ $O( 1 )$ 回ずつ参照するので $\Theta( n )$ 時間で動作します．
コード (C++)
int dfs( const VVI &G, const int K, const int u, const int p = -1 ) { VI ch; FOR( v, G[u] ) { if ( v == p ) { continue; } const int val = dfs( G, K, v, u ); if ( val == -1 ) { return -1; } if ( 0 < val ) { ch.PB( val ); } } const int sum = accumulate( ALL( ch ), 0 ); switch ( SZ( ch ) ) { case 0: return K == 1 ? 0 : 1; case 1: return sum == K - 1 ? 0 : sum + 1; case 2: return sum == K - 1 ? 0 : -1; } return -1; } int main() { IN( int, N, K ); VVI G( N * K ); REP( N * K - 1 ) { IN( int, u, v ); --u, --v; G[u].PB( v ); G[v].PB( u ); } cout << YESNO( dfs( G, K, 0 ) == 0 ) << endl; return 0; }
コード (Haskell)
main = do [ n, k ] <- readInts g <- accumArray ( flip (:) ) [] ( 1, n * k ) . concatMap ( \[ u, v ] -> [ ( u, v ), ( v, u ) ] ) <$> replicateM ( n * k - 1 ) readInts putStrLn $ yesno $ maybe False ( == Right () ) $ dfs g k 1 (-1) dfs g k u p = do ch <- sequence $ do v <- g ! u guard $ v /= p return $ dfs g k v u let ( s, sz ) = ( sum &&& length ) $ lefts ch case sz of 0 -> Just $ if k == 1 then Right () else Left 1 1 -> Just $ if s == k - 1 then Right () else Left $ s + 1 2 -> if s == k - 1 then Just $ Right () else Nothing _ -> Nothing
