번부터 번까지 번호가 붙은 정점 개로 이루어진 트리가 있다. 각 정점 에는 양의 정수 가 적혀 있다.
두 정점 에 적힌 값이 같으면, 즉 이면 트리에서 와 를 잇는 경로를 하나 선택할 수 있다. 선택한 경로에는 양 끝 정점과 그 사이의 모든 정점이 포함된다.
양 끝 정점에 적힌 값만 같으면 되며, 중간 정점의 값은 무엇이든 상관없다. 예를 들어 으로 이어진 트리에서 값이 차례대로 이라면, 세 정점을 모두 포함하는 경로 을 선택할 수 있다.
같은 정점을 양 끝으로 선택하는 것도 허용한다. 이 경우 경로는 정점 하나로만 이루어져 있다.
다음 조건을 모두 만족하도록 경로들을 선택하려고 한다.
모든 간선을 사용할 필요는 없다. 경로는 원래 트리의 간선을 따라 이어지며, 새 간선을 추가하는 것은 아니다.
필요한 경로의 최소 개수를 구하여라. 각 정점을 정점 하나짜리 경로로 선택하면 항상 조건을 만족시킬 수 있다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 필요한 경로의 최소 개수를 한 줄에 출력한다.
첫 번째 케이스에서는 경로 하나로 모든 정점을 덮는다. 양 끝의 값은 모두 이고, 중간 정점의 값 은 상관없다. 두 번째 케이스에서는 경로 과 정점 하나짜리 경로 를 고르면 된다. 두 경로는 정점을 공유하지 않고, 각 경로의 양 끝 값도 같다. 모든 정점을 한 경로로 덮을 수는 없으므로 답은 이다. 세 번째 케이스에서는 유일한 정점 자체가 경로 하나가 된다.
첫째 줄에 테스트 케이스의 수 가 주어진다. 각 케이스는 다음과 같은 형식으로 주어진다.
각 케이스의 첫째 줄에 정점의 수 이 주어진다. 둘째 줄에 각 정점에 적힌 값 이 주어진다.
다음 개의 줄 중 번째 줄에는 번 정점과 번 정점을 잇는 간선이 주어진다. 이면 간선을 나타내는 줄은 주어지지 않는다.
| 3 | 14 | , (). |
| 4 | 18 | 각 테스트 케이스에서 이고, 모든 테스트 케이스에 대한 의 합이 이하이다. |
| 5 | 22 | 각 테스트 케이스에서 이고, 모든 테스트 케이스에 대한 의 합이 이하이다. |
| 6 | 31 | 추가적인 제약이 없다. |
경로 와 정점 하나짜리 경로 , 을 선택하면 세 경로로 덮을 수 있다. 경로 도 양 끝 값이 같지만, 와 정점 를 공유하므로 두 경로를 함께 고를 수 없다. 두 개 이하의 경로로는 모든 정점을 덮을 수 없다.
서로 다른 두 정점에 같은 값이 적혀 있지 않으므로 모든 정점을 각각 정점 하나짜리 경로로 선택해야 한다.
