tree dp2 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. Codeforces #627 div3 F - Maximum white subtree (graph dp, reroot) https://codeforces.com/contest/1324/problem/F reroot 첫 성공 무방향트리가 주어진다. 각 정점마다 하얀색(1)또는 검은색(0)으로 색칠되어 있다. i번 정점을 포함하는 서브트리 중 하얀색정점의 개수 - 검은색 정점의 개수가 최대인 경우 그 값을 각각 구해라 (i=1,2,3,4...n) 1번 정점을 root로 하는 전체 트리에서 dp[u] : u를 포함한 서브트리에서 cntw-cntb 최대값 u에 인접한 v에 대해 ans[v] = dp[v] + max(dp[u],0)이다. v에서원하는 값 ans[v]가 u,v에대한 상태로만 정의되므로 reroot 적용가능하다. dp[u] -= max(dp[v],0) dp[v] += max(dp[u],0) go(u,v) dp[u] =.. 2020. 3. 14. 이전 1 다음
