026 - Independent Set on a Tree（★4）

2025-11-29

問題

解答

提出 #71288229

type I = [[Int]]
type O = [Int]

solve :: I -> O
solve ([n]:xss) = take (n `div` 2) x
    where
        g = toGraph (1, n) xss
        dst = dfs (1, n) g 1
        x1 = map fst . filter (\(idx,d) -> odd d) . assocs $ dst
        x2 = map fst . filter (\(idx,d) -> even d) . assocs $ dst
        x = if length x1 > length x2 then x1 else x2

頂点1からの距離が奇数となる頂点のリストと偶数の頂点のリストのうち、大きい方のリストの先頭からn/2個を出力する。