정점이 개인 트리가 주어진다. 처음에 각 정점에는 이 적혀 있다.
당신은 각 정점에 대해 최대 한 번씩 다음 시행을 할 수 있다.
정점 하나를 고른 후, 그 정점에 적힌 수를 인접한 정점에 적힌 수 중 가장 작은 수 로 바꾼다.
만약 고른 정점에 인접한 정점이 없다면, 인접한 정점에 적힌 수 중 가장 작은 수는 으로 간주한다.
시행들을 적절한 순서로 수행했을 때, 트리에 적힌 수들의 합의 최댓값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
트리에 적힌 수들의 합의 최댓값을 출력한다.
유일한 정점에 시행을 하면 적힌 수가 이 된다.
먼저 번 정점에 시행을 하면 이 된다. 이후 번, 번 정점에 시행을 하면 두 정점은 각각 가 된다. 합은 이다.
주어지는 그래프는 개의 정점을 가진 트리이다. 정점은 번부터 번까지 번호가 매겨져 있다.
번 정점에 먼저 시행을 하면 이 된다. 이후 번 정점에 시행을 하면 세 정점은 각각 가 된다. 합은 이다.
