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
| #include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 300005
vector<int>to[maxn];
int n,times;
int siz[maxn],dfn[maxn],son[maxn],ss[maxn],fa[maxn][21],lg[maxn],p[maxn];
struct node{
int l,r,flag;
node(int a=0,int b=0,int c=0) {l=a;r=b;flag=c;}
};
vector<node>O[maxn];
void dfs(int x,int pre) {
fa[x][0]=pre;siz[x]=1;dfn[x]=++times;p[times]=x;son[x]=ss[x]=0;
for (int i=1;i<=19;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for (auto y:to[x]) if (y^pre) {
dfs(y,x);siz[x]+=siz[y];
if (siz[son[x]]<=siz[y]) ss[x]=son[x],son[x]=y;
else if (siz[ss[x]]<=siz[y]) ss[x]=y;
}
}
struct BIT{
#define lowbit(x) ((x)&(-x))
int f[maxn];
void add(int x,int y) {for (;x<=n;x+=lowbit(x)) f[x]+=y;}
int query(int x) {int sum=0;x=max(x,0);for (;x;x-=lowbit(x)) sum+=f[x];return sum;}
}t;
int calcsiz(int x,int y) {
if (dfn[x]<=dfn[y]&&dfn[y]<dfn[x]+siz[x]) return siz[x]-siz[y];
return siz[x];
}
void solve(void) {
int i,x,j,y;ll ans=0;times=0;
read(n);
for (i=1;i<=n;i++) O[i].clear(),to[i].clear();
for (i=1;i<n;i++) read(x),read(y),to[x].push_back(y),to[y].push_back(x);
dfs(1,0);
for (i=2;i<=n;i++) {
x=p[(dfn[i]+dfn[i]+siz[i])/2];
if (siz[i]-siz[x]>siz[i]/2) {
for (j=20;j>=0;j--) if (dfn[fa[x][j]]>=dfn[i]&&siz[i]-siz[fa[x][j]]>siz[i]/2) x=fa[x][j];
x=fa[x][0];
}
if (dfn[x]<dfn[i]) continue;
int Max=siz[son[x]];
if (Max<=siz[i]/2) ans+=x;
x=fa[x][0];if (dfn[x]<dfn[i]) continue;
Max=siz[son[x]];
if (Max<=siz[i]/2) ans+=x;
}
for (i=2;i<=n;i++) {
int tmp=(2+n-siz[i])/2;
if (tmp<dfn[i]) x=p[tmp];
else x=p[tmp-dfn[i]+(dfn[i]+siz[i])];
if (n-calcsiz(x,i)-siz[i]>(n-siz[i])/2) {
for (j=20;j>=0;j--) if (fa[x][j]&&n-calcsiz(fa[x][j],i)-siz[i]>(n-siz[i])/2) x=fa[x][j];
x=fa[x][0];
}
if (!x) continue;
int Max=max(calcsiz(son[x],i),calcsiz(ss[x],i));
if (Max<=(n-siz[i])/2) ans+=x;
x=fa[x][0];if (!x) continue;
Max=max(calcsiz(son[x],i),calcsiz(ss[x],i));
if (Max<=(n-siz[i])/2) ans+=x;
}
printf("%lld\n",ans);
}
signed main(void){
int T;
read(T);
while (T--) solve();
return 0;
}
|