1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| #include<bits/stdc++.h>
#define REG register
#define MAXN 300005
#define LL long long
#define FORE(i,now) for(REG int i=head[now];i;i=ed[i].nxt)
using namespace std;
inline int read(){
REG int x(0);
REG char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x*10)+(c^48),c=getchar();
return x;
}
inline void Swap(int& a,int& b){int t=a;a=b,b=t;}
int T,n;
struct Edge{
int v,nxt;
}ed[MAXN<<1];
int head[MAXN],cnt;
inline void adde(int u,int v){
ed[++cnt]=(Edge){v,head[u]};
head[u]=cnt;
}
inline void add(int u,int v){
adde(u,v),adde(v,u);
}
int s[MAXN],g[MAXN],Dir[MAXN],rt,Fir,Sec;
LL ans;
struct t{
int c[MAXN];
inline void Clear(){memset(c,0,sizeof c);}
inline void Upd(int pos,int k){++pos;for(;pos<=n+1;pos+=pos&-pos)c[pos]+=k;}
inline int Ask(int pos){++pos;int ans=0;for(;pos;pos-=pos&-pos)ans+=c[pos];return ans;}
}c1,c2;
void Find_rt(int now,int fa){
s[now]=1,g[now]=0;
FORE(i,now){
int v=ed[i].v;
if(v==fa) continue;
Find_rt(v,now);
s[now]+=s[v];
if(s[v]>g[now]) g[now]=s[v];
}
if(g[now]<=(n>>1)&&n-s[now]<=(n>>1)) rt=now;
}
void ReBuild(int now,int fa){
s[now]=1,g[now]=0;
FORE(i,now){
int v=ed[i].v;
if(v==fa) continue;
ReBuild(v,now);
s[now]+=s[v];
if(s[v]>g[now]) g[now]=s[v];
}
}
void Solve(int now,int fa){
c1.Upd(s[now],-1),c1.Upd(n-s[now],1),c2.Upd(s[now],1);
Dir[now]|=Dir[fa];
if(now^rt){
ans+=(LL)now*(c1.Ask(n-2*g[now])-c1.Ask(n-2*s[now]-1));
ans+=(LL)now*(c2.Ask(n-2*g[now])-c2.Ask(n-2*s[now]-1));
ans+=(LL)rt*(s[now]<=n-2*s[Dir[now]?Sec:Fir]);
}
FORE(i,now){
int v=ed[i].v;
if(v==fa) continue;
Solve(v,now);
}
if(now^rt)
ans-=(LL)now*(c2.Ask(n-2*g[now])-c2.Ask(n-2*s[now]-1));
c1.Upd(s[now],1),c1.Upd(n-s[now],-1);
}
void Init(){
memset(head,0,sizeof head);
memset(Dir,0,sizeof Dir);
cnt=0;
c1.Clear(),c2.Clear();
Fir=Sec=ans=0;
n=read();
for(REG int i=1;i<n;++i) add(read(),read());
Find_rt(1,0);
ReBuild(rt,0);
FORE(i,rt){
int v=ed[i].v;
if(s[v]>s[Sec]) Sec=v;
if(s[Sec]>s[Fir]) Swap(Fir,Sec);
}
for(REG int i=1;i<=n;++i) c1.Upd(s[i],1);
Dir[Fir]=1;
Solve(rt,0);
}
int main(){
T=read();
while(T--){
Init();
printf("%lld\n",ans);
}
}
|
