19530번 - 숭고한 마라톤 대회 출처분류

숭고한 연합에서는 알고리즘 마라톤 대회를 개최하기 위해 적당한 장소를 선정했다. 이 장소는 N개의 교차로와 N-1개의 양방향 도로들로 이루어져 있고, 모든 서로 다른 교차로 쌍 사이에 정확히 하나의 경로가 존재한다. (다시 말해, 이 장소는 트리 구조이다.)

명색이 알고리즘 마라톤이므로 주자들이 머릿속으로 최단경로 알고리즘을 돌리면서 달릴 수 있도록 다양한 코스가 존재하면 좋을 것이다. 따라서 서로 다른 두 교차로를 잘 골라서 각각 시작 교차로와 끝 교차로로 선정했을 때, 숭실대/고려대/한양대 세 학교가 시작 교차로에서 끝 교차로로 가는 겹치지 않는 세 개의 경로를 정할 수 있도록 하는 것이 목표이다. 어떤 두 경로가 겹치지 않으려면 시작 교차로와 끝 교차로를 제외하고는 공유하는 교차로가 없어야 한다.

목표를 달성할 수 있게 장소에 정확히 2개의 도로를 추가할 것이다. 어떤 도로들을 추가할지 정하는 방법이 몇 가지나 있는지 알려주자. 방법의 수가 너무 많을 수 있으므로 10⁹+7로 나눈 나머지를 출력하라. 도로 추가 이후 두 교차로 사이에는 최대 하나의 도로만 존재해야 하고, 어떤 도로도 양 끝 교차로가 같아서는 안 된다. (다시 말해, 단순 그래프이어야 한다.)

방법 1의 경우: 2를 시작 교차로로, 3을 끝 교차로로 정하면 3개의 서로 겹치지 않는 경로가 생긴다.

방법 2의 경우: 1을 시작 교차로로, 2를 끝 교차로로 정하면 3개의 서로 겹치지 않는 경로가 생긴다.

방법 3의 경우: 2를 시작 교차로로, 4를 끝 교차로로 정하면 3개의 서로 겹치지 않는 경로가 생긴다.

따라서 주어진 트리에서 가능한 방법은 3가지이고 정답은 3이 된다.

첫 번째 줄에 교차로의 개수 N이 주어진다. (4 ≤ N ≤ 500,000)

두 번째 줄부터 N-1개의 줄에 걸쳐 각 도로가 연결하는 두 교차로의 번호 a,b가 공백으로 구분되어 주어진다. (1 ≤ a,b ≤ N)

주어지는 입력은 트리임이 보장된다.

목표를 달성할 수 있게 도로 2개를 정하는 방법의 수를 10⁹+7로 나눈 나머지를 출력한다.