트리의 최대 독립 집합

정점에 가중치가 있는 트리가 주어진다. 독립 집합은 어떤 두 정점도 간선으로 직접 연결되어 있지 않은 정점들의 집합이다. 독립 집합의 크기는 그 집합에 포함된 정점들의 가중치 합이다. 빈 집합의 크기는 0이다.

주어진 트리에서 가중치 합이 가장 큰 독립 집합을 구하라.

첫째 줄에 정점의 수 n이 주어진다. n은 10,000 이하의 양의 정수이다. 정점 번호는 1부터 n까지이다.

둘째 줄에는 각 정점의 가중치 w_1, w_2, ..., w_n이 주어진다. w_i는 정점 i의 가중치이며, 모든 가중치는 10,000 이하의 자연수이다.

셋째 줄부터 n-1개의 줄에는 트리의 간선이 한 줄에 하나씩 주어진다. 각 간선은 서로 연결된 두 정점 번호로 주어진다. 입력의 모든 정수 사이에는 공백이 하나 있다.

첫째 줄에 최대 독립 집합의 가중치 합을 출력한다.

둘째 줄에는 그 독립 집합에 속한 정점을 오름차순으로 출력한다. 최대 독립 집합이 여러 개이면 그중 하나만 출력하면 된다.