Description
[sum_{(u,v)in E}Biggl(sum_{x为S_u重心}x+sum_{y为S_v重心}yBiggr)
]
(1leqslant nleqslant 300000)
Solution
退役选手居然还能不看题解过题。
首先容易看出一定是对于每个点统计它可以作为几个重心，断掉的边一定在某个子树中，设重心为 (u) ，子树为 (v) ，(u) 其他出边 (siz) 最大为 (maxsiz) ，和为 (sumsiz) ，(v) 大小为 (vsiz) ，砍掉部分为 (s) ，则有 (max(maxsiz,vsiz-s)leqslantlfloorfrac{n-s}2 floor) ，然后分类讨论一下其实是 (vsiz imes 2-nleqslant sleqslant n-maxsiz imes 2) ，于是不难想到用线段树维护 (s) 的集合，这时可以写出一个可持久化线段树合并 (+) 二次扫描与换根的做法，实际写的时候会发现二次扫描时根本没有合并，于是用一个树状数组进入回溯时修改即可。
Code
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int res = 0;
char c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c))
{
res = (res << 1) + (res << 3) + c - '0';
c = getchar();
}
return res;
}
#define MAXN 300000
int n;
struct edge
{
int to,nxt;
}e[MAXN << 1];
int edgenum = 0,lin[MAXN] = {0};
void add(int a,int b)
{
e[++edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;
e[++edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;
return;
}
#define mid ((l + r) >> 1)
struct node
{
int lc,rc,sum;
}t[MAXN * 60];
int ptr = 0;
int newnode(){return ++ptr;}
int root[MAXN];
void insert(int &rt,int p,int val,int l,int r)
{
if(rt == 0)rt = newnode();
if(l == r){t[rt].sum += val;return;}
if(p <= mid)insert(t[rt].lc,p,val,l,mid);
else insert(t[rt].rc,p,val,mid + 1,r);
t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;
return;
}
int merge(int a,int b,int l,int r)
{
if(a == 0 || b == 0)return a + b;
if(l == r){t[a].sum += t[b].sum;return a;}
t[a].lc = merge(t[a].lc,t[b].lc,l,mid);
t[a].rc = merge(t[a].rc,t[b].rc,mid + 1,r);
t[a].sum = t[t[a].lc].sum + t[t[a].rc].sum;
return a;
}
int query(int rt,int L,int R,int l,int r)
{
if(rt == 0)return 0;
if(L <= l && r <= R)return t[rt].sum;
int res = 0;
if(L <= mid)res += query(t[rt].lc,L,R,l,mid);
if(R > mid)res += query(t[rt].rc,L,R,mid + 1,r);
return res;
}
long long ans = 0;
int siz[MAXN];
int sum[MAXN];
int c[MAXN];
int lowbit(int x){return x & (-x);}
void qadd(int p,int x){for(int i = p;i <= n;i += lowbit(i))c[i] += x;return;}
int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}
int query(int l,int r)
{
l = max(l,1);r = min(r,n);
return query(r) - query(l - 1);
}
void init()
{
edgenum = 0;
memset(lin,0,sizeof(lin));
ans = 0;
memset(siz,0,sizeof(siz));
ptr = 0;
memset(t,0,sizeof(t));
memset(root,0,sizeof(root));
memset(sum,0,sizeof(sum));
memset(c,0,sizeof(c));
return;
}
int premax[MAXN],sufmax[MAXN];
vector<int> v;
int fa[MAXN];
void calc1(int k)
{
siz[k] = 1;
for(int i = lin[k];i != 0;i = e[i].nxt)
{
if(e[i].to == fa[k])continue;
fa[e[i].to] = k;
calc1(e[i].to);
siz[k] += siz[e[i].to];
}
insert(root[k],siz[k],1,1,n);
v.clear();v.push_back(0);
for(int i = lin[k];i != 0;i = e[i].nxt)if(e[i].to != fa[k])v.push_back(e[i].to);
int cnt = v.size() - 1;
sufmax[cnt + 1] = 0;
for(int i = 1;i <= cnt;++i)premax[i] = max(premax[i - 1],siz[v[i]]);
for(int i = cnt;i >= 1;--i)sufmax[i] = max(sufmax[i + 1],siz[v[i]]);
for(int i = 1;i <= cnt;++i)
{
int maxsiz = max(max(premax[i - 1],sufmax[i + 1]),n - siz[k]);
sum[k] += query(root[v[i]],siz[v[i]] * 2 - n,n - maxsiz * 2,1,n);
}
for(int i = lin[k];i != 0;i = e[i].nxt)if(e[i].to != fa[k])root[k] = merge(root[k],root[e[i].to],1,n);
if(k != 1)
{
int maxsiz = 0;
for(int i = lin[k];i != 0;i = e[i].nxt)if(e[i].to != fa[k])maxsiz = max(maxsiz,siz[e[i].to]);
int L = (n - siz[k]) * 2 - n,R = n - maxsiz * 2;
sum[k] -= query(root[k],L,R,1,n);
}
return;
}
void calc2(int k)
{
if(k != 1)
{
qadd(siz[k],-1);
qadd(n - siz[k],1);
}
for(int i = lin[k];i != 0;i = e[i].nxt)
{
if(e[i].to == fa[k])continue;
calc2(e[i].to);
}
if(k != 1)
{
int maxsiz = 0;
for(int i = lin[k];i != 0;i = e[i].nxt)if(e[i].to != fa[k])maxsiz = max(maxsiz,siz[e[i].to]);
int L = (n - siz[k]) * 2 - n,R = n - maxsiz * 2;
qadd(siz[k],1);
qadd(n - siz[k],-1);
sum[k] += query(L,R);
if(maxsiz == 0)--sum[k];
if((n - siz[k]) * 2 - n <= n - siz[k] && n - siz[k] <= n - maxsiz * 2)++sum[k];
}
return;
}
void solve()
{
init();
n = read();
for(int i = 1;i < n;++i)add(read(),read());
calc1(1);
for(int i = 1;i <= n;++i)qadd(i,query(root[1],i,i,1,n));
calc2(1);
for(int k = 1;k <= n;++k)ans += 1ll * k * sum[k];
cout << ans << endl;
return;
}
int main()
{
int testcases = read();
while(testcases--)solve();
return 0;
}