graph dp1 cf 551 div2 D - Serval and Rooted Tree (tree, dp, 발상) https://codeforces.com/contest/1153/problem/D 문제를 재정의하는 방법이 새로워서 리뷰 루트가 1인 트리가 주어진다. 리프노드가 k개 있다면 각 리프노드에 1~k의 순열을 저장할 수 있다. 각 노드마다 min또는 max 성질이 주어지는데, 자식노드의 값중 최소 또는 최대를 값으로 갖는다는 의미다. 리프노드에 적절한 값을 넣어 루트에 저장될 수 있는 값 중 최대를 구하라. 현재 정점 u가 max 성질이 있다면, 그냥 자식 정점 값중 최대를 갖으면 된다. 문제가되는건 min성질이다. 예를들어서 min성질을 갖는 정점 u가 리프노드 3개를 자식으로 둔다면, 가장 작은 하나를 제외하고 2개의 숫자를 잃는다고 생각할 수 있다.(잘 생각해보면 u의 자식이 리프노드가 아니더라도 일반.. 2020. 3. 25. 이전 1 다음
