두 트리

시간 제한8초메모리 제한256 MB

요약

같은 n개 정점으로 이루어진 두 트리가 주어질 때, 모든 정점 쌍에서 두 트리 거리의 합을 제곱하여 더한 값을 2^32로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 트리, 분할 정복, 수학
정답자: 아직 제출이 없습니다

문제

트리 $T_1$ 과 $T_2$ 가 주어진다. 두 트리는 모두 1번부터 $n$ 번까지 번호가 붙은 정점 $n$ 개로 이루어진다. 트리 $T$ 에서 정점 $v$ 와 $u$ 사이 경로의 간선 수를 $d(v, u, T)$ 라고 하자. 다음 합을 구하라.

$\sum_{1 \le u < v \le n} \left(d(v, u, T_1) + d(v, u, T_2)\right)^2$

답이 클 수 있으므로 $2^{32}$ 로 나눈 나머지를 출력하라.

입력

첫 줄에 정수 $n$ 이 주어진다. 이는 각 트리의 정점 수이며 $1 \le n \le 100000$ 이다. 다음 $n-1$ 개 줄에는 트리 $T_1$ 에서 간선으로 연결된 두 정점 $u$ 와 $v$ 가 주어진다( $1 \le u, v \le n$ ). 마지막 $n-1$ 개 줄에는 트리 $T_2$ 에서 간선으로 연결된 두 정점 $u$ 와 $v$ 가 주어진다( $1 \le u, v \le n$ ).

출력

답을 $2^{32}$ 로 나눈 나머지를 출력하라.

예제2

예제 1
입력
```
3
1 2
1 3
1 2
1 3
```
예상 출력
```
24
```
예제 2
입력
```
3
1 2
1 3
1 2
2 3
```
예상 출력
```
22
```