대전 도시철도 2호선

면접 대비

시간 제한1초메모리 제한1024 MB

요약

트리에서 1번과 N번을 잇는 경로에 없는 교차로 두 개를 고르고, 둘 사이의 경로가 그 경로와 한 번이라도 만나는 경우의 수를 셉니다.

난이도: 보통10점 중 4점
유형: 트리, DFS, 조합론
정답자: 아직 제출이 없습니다

문제

대전시에는 교차로 $N$ 개와 도로 $N-1$ 개가 있으며, 이들은 트리 구조를 이룬다. 교차로는 1번부터 $N$ 번까지 번호가 매겨져 있다. 대전시는 1번 교차로와 $N$ 번 교차로를 잇는 경로를 따라 대전 도시철도 1호선을 운행하고 있다. 이 경로에 포함된 교차로에는 역이, 도로에는 철도가 설치되어 있다.

대전시는 도시철도 2호선을 추가로 운행하려고 한다. 1호선과 마찬가지로 2호선도 $S$ 번 교차로와 $E$ 번 교차로를 잇는 경로를 따라 역과 철도를 설치한다. $S$ 번과 $E$ 번 교차로는 서로 달라야 하며, 1호선 역이 설치되지 않은 교차로여야 한다. 또한 이용객이 1호선으로 환승할 수 있도록 2호선은 1호선 역을 적어도 하나 포함해야 한다.

위 조건을 만족하는 두 교차로를 고르는 경우의 수를 구하라. 두 교차로의 순서만 바꾼 경우는 같은 경우로 본다.

입력

첫째 줄에 정수 $N$ ( $4 \le N \le 100000$ )이 주어진다. 둘째 줄부터 $N-1$ 개의 줄에 도로가 연결하는 양 끝 교차로의 번호 $u, v$ ( $1 \le u, v \le N$ ; $u \ne v$ )가 공백으로 구분되어 주어진다.

출력

조건을 만족하는 두 교차로를 고르는 경우의 수를 출력한다.

예제3

예제 1
입력
```
4
2 1
1 4
4 3
```
예상 출력
```
1
```
예제 2
입력
```
4
1 4
4 2
2 3
```
예상 출력
```
0
```
예제 3
입력
```
7
1 2
2 3
1 4
1 5
5 6
5 7
```
예상 출력
```
5
```