dlwocks31의 PS일기장

RTG3 C 로 만난 문제이다. 시도 처음 봤을 때는 n이 작으니 어떻게든 모든 가능한 트리를 다 순회해보면 되지 않을까? 하는 생각이 들었다. 모든 가능한 parent assginment를 다 시도해보면 \((n-1)^{n-1}\)이라 안되고, 트리에 dfs in/out기록을 토대로 만들 수 있는 2n짜리 bracket sequence? 같은걸 순회해볼 생각도 했다. 이건 \( n\cdot 2^{2n-2} \) 정도의 비벼볼만한 시간복잡도가 나오는데 이렇게 카운트하면 children의 순서가 바뀌면 다른 트리로 카운트된다는 것을 깨닫고 그 중복을 없애볼 생각을 하다가 너무 어려워서 포기했다. 풀이과정 우선 풀이의 첫 몇줄에서 (\(dp_{i, bm}\) = i를 루트로 하고 bm(bitmask의 약자)..