2213_트리의 독립집합

https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 문제에 나온 트리는 1번을 루트노드라고 생각한다면 위와 같은 구성을 가지게 된다. 그렇다면 어떻게 하면 가중치를 더해갈 수 있을지 생각해보자. 먼저 자식부터 검사를 하는 것이 좋을 것이다. 5->4->3->7->6->2->1 순서로 탐색을 한다. 어떤부분을 탐색할때 자식노드와 부모 노드가 있다고 생각하면, 부모노드가 독립집합 안에 속해있다면 자식노드는 속할 수 없고..