dfs dp1 Educational codeforces 67 div2 E - tree painting (dfs, dp, rerooting, tree) https://codeforces.com/contest/1187/problem/E 항상 궁금했던 그래프+dp 유형. editorial피셜로 기본문제라고 한다. https://suuntree.tistory.com/126?category=805933 트리에서 모든정점 사이즈 선형시간에 구하는 법 트리가 주어진다. 임의의 정점 하나를 선택한다. 그 정점을 루트로 취급할 때 그 서브트리의 모든 정점들의 size합을 구한다. 그 값 중 최대를 구해라. dp[u] : u를 트리의 루트로 봤을 때 모든 정점의 사이즈 합 위 예시와 같이 루트를 바꿨을 때 dp값이 바뀔 여지가 있다. dp값이 바뀐다면 참조투명하지 않다는 것인데, rerooting 테크닉을 사용하여 이를 극복하는 것에 유념하여 보면 된다. 일단 직관적으.. 2020. 1. 21. 이전 1 다음
