：你知道吗，章鱼和蜘蛛是很接近的哦。
：你是指八条腿？还是都在漫威宇宙中出现？
：我指的是她们在家谱树的距离只有三！
题目描述
最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。
Sakiko 有一棵无根树，她定义 f（i,j）f（i,j） 是以 ii 为根的情况下，一对节点的LCA为 jj 的节点对数，Sakiko 想知道 ∑i=1nf（i,1）∑i=1nf（i,1） 到 ∑i=1nf（i,n）∑i=1nf（i,n） 的值。
第一行输入一个正整数 T（1≤T≤2×105）T（1≤T≤2×105） ，表示数据组数。
对于每一组数据：
第一行输入一个整数 n（1≤n≤2×105）n（1≤n≤2×105） ，表示树节点个数。
接下来 n−1n−1 行，每行输入两个整数 u,v（1≤u,v≤n）u,v（1≤u,v≤n） ，表示树上的边。
数据保证 ∑n≤2×106∑n≤2×106 。
1
3
1 2
2 35 8 5
根为1时：
LCA为1的节点对：（1,1）,（1,2）,（1,3）
LCA为2的节点对：（2,2）,（2,3）
LCA为3的节点对：（3,3）
根为2时：
LCA为1的节点对：（1,1）
LCA为2的节点对：（1,2）,（1,3）,（2,2）,（2,3）
LCA为3的节点对：（3,3）
根为3时：
LCA为1的节点对：（1,1）
LCA为2的节点对：（1,2）,（2,2）
LCA为3的节点对：（1,3）,（2,3）,（3,3）
因此答案为[3+1+1,2+4+2,1+1+3] = [5,8,5]