삼각형 트리

어느 날 시골에 거대한 나무가 자랐다. 어린 존은 어릴 때부터 키운 독수리와 함께 이 나무를 자기 집으로 삼기로 했다. 존은 아연 도금한 정사각형 강철 막대로 나무 위에 구조물을 지을 예정이다. 그러나 그는 물리적으로 불가능한 구조물은 지을 수 없다는 사실을 몰랐다.

루트가 있는 트리$^1$가 주어진다. 트리의 정점은 $n$개이고 정점 $1$이 루트이다. 두 정점 $(u,v)$가 다음 조건을 만족하면 이를 좋은 쌍이라고 한다. $u$가 $v$의 조상$^2$이 아니고, $v$도 $u$의 조상이 아니다. 두 정점 $u$, $v$에 대해 $\text{dist}(u,v)$는 $u$에서 $v$로 가는 유일한 단순 경로의 간선 수이다. $\text{lca}(u,v)$는 $u$와 $v$의 최소 공통 조상이다.

함수 $f(u,v)$는 다음과 같이 정의한다.

• $(u,v)$가 좋은 쌍이면, $f(u,v)$는 변의 길이가 $\text{dist}(u,\text{lca}(u,v))$, $\text{dist}(v,\text{lca}(u,v))$, $x$인 퇴화되지 않은 삼각형$^3$이 만들어지는 정수 $x$의 개수이다.
• 그렇지 않으면 $f(u,v)=0$이다.

구해야 하는 값은 $\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} f(i,j)$이다.

1 트리는 사이클이 없는 연결 그래프이다. 루트가 있는 트리는 정점 하나를 루트로 특별히 정한 트리이다.

2 정점 $v$의 조상은 $v$에서 루트까지 가는 단순 경로 위의 정점 중 $v$ 자신을 제외한 정점이다. 루트도 포함한다. 루트에는 조상이 없다.

3 변의 길이가 $a$, $b$, $c$인 삼각형이 퇴화되지 않으려면 $a+b>c$, $a+c>b$, $b+c>a$를 모두 만족해야 한다.

첫 번째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^4$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

테스트 케이스의 첫 줄에 정수 $n$ ($1 \le n \le 3 \cdot 10^5$)이 주어진다.

이어지는 $n-1$개의 줄에 간선의 양 끝 정점 $u_i$, $v_i$ ($1 \le u_i,v_i \le n$, $u_i \neq v_i$)가 주어진다. 주어진 간선들은 트리를 이룬다.

모든 테스트 케이스의 $n$의 합은 $3 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 답을 한 줄에 출력한다.

첫 번째 테스트 케이스에서 $i<j$를 만족하는 좋은 쌍은 $(2,3)$뿐이다. $\text{lca}(2,3)$은 $1$이고, 두 거리는 모두 $1$이다. 길이가 $1$, $1$인 두 변으로 만들 수 있는 $x$는 $1$뿐이므로 첫 번째 테스트 케이스의 답은 $1$이다.

두 번째 테스트 케이스에는 좋은 쌍이 없으므로 답은 $0$이다.

세 번째 테스트 케이스에서 $i<j$를 만족하는 좋은 쌍은 다음과 같다.

• $(2,5)$: $\text{lca}(2,5)$는 $1$이고, 두 거리는 $1$, $1$이다. 가능한 $x$는 $1$뿐이다.
• $(3,4)$: $\text{lca}(3,4)$는 $2$이고, 두 거리는 $1$, $1$이다. 가능한 $x$는 $1$뿐이다.
• $(3,5)$: $\text{lca}(3,5)$는 $1$이고, 두 거리는 $2$, $1$이다. 가능한 $x$는 $2$뿐이다.
• $(4,5)$: $\text{lca}(4,5)$는 $1$이고, 두 거리는 $2$, $1$이다. 가능한 $x$는 $2$뿐이다.

따라서 세 번째 테스트 케이스의 답은 $1+1+1+1=4$이다.