CF1 cf 564 div2 D - Nauuo and circle (tree, graph dp) https://codeforces.com/contest/1173/problem/D 정확하지 않은 잘못된 점화식을 쓰려다 실패 최대 2e5의 정점 n개를 갖는 트리가 주어진다. 정점을 원위에 일정한 간격으로 배치했을 때 간선이 교차하지 않는 경우의 수를 구하라. n=4, edge = {(1,2), (1,3), (2,4)}인 경우 8. 아래 그림 참조 원의 맨 위를 1로 고정(전체드리의 루트 고정)시킨 후 경우의수를 구해서 마지막에 n을 곱하자 f(u) : u를 루트로하는 서브트리를 간선이 교차하지 않도록 배치하는 경우의 수 (각각의 자식노드를 루트로 하는 서브트리(sub(v))를 비어있는 원 위에 순서대로 배치하면 된다. 이 때, 각각의 칸 안에도 sub(v)의 루트와 그 자식들이 순서대로 배치돼야 한다... 2020. 3. 15. 이전 1 다음