Data.Tree.levels が使える

競プロ典型 90 問 26 日目 - Independent Set on a Tree（★4）

import Control.Monad
import qualified Data.ByteString.Char8 as C
import Data.Graph
import Data.List
import Data.Tree

main = prs >>= fmt . sol

prs = readLn >>= \n -> (n,) <$> replicateM (n-1) ints

ints = unfoldr (C.readInt . C.dropWhile (==' ')) <$> C.getLine

fmt = putStrLn . unwords . map show

sol (n,es) = take (n `div` 2) $ if length l0>length l1 then l0 else l1
  where
  g = buildG (1,n) $ concatMap (\[u,v] -> [(u,v),(v,u)]) es
  t = head $ dfs g [1]
  (l0,l1) = go ([],[]) True $ levels t

go (l0,l1) _ [] = (l0,l1)
go (l0,l1) True (l:ls) = go (l++l0,l1) False ls
go (l0,l1) False (l:ls) = go (l0,l++l1) True ls