zcmimi's blog

查看原题

点击跳转

既然对考虑每条边断开后产生的重心比较麻烦,那么换个方式:

考虑每个点成为重心的次数

首先找出重心作为树根

设当前节点为x,子树大小为siz_x,孩子的最大子树大小为g_x,割掉一条边后,另一棵树大小为S

考虑x不是重心的情况:

2(n-S-siz_x)\le n-S2g_x\le n-S

也就是

S\in [n-2siz_x,n-2g_x]

我们可以用树状数组维护并统计每个点割掉与父亲之间的边后形成的S

显然这条边不能在x的子树内,那么减去 进入x子树前后求和的差

考虑x为重心的情况:

ux重儿子,vx次重儿子

若割掉的边在u的子树中: 2siz_v\le n-S,即S\le n-2siz_v

否则: 2siz_u\le n-S,即S\le n-2siz_u

#include<bits/stdc++.h>
const int N=300011;
int T,n,cnt,head[N],rt,siz[N],g[N];
struct edge{int to,nxt;}e[N*2];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
#define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
void cmax(int&x,int y){if(y>x)x=y;}
void dfs(int x,int f){
    siz[x]=1,g[x]=0;
    bool ff=0;
    fl(i,x)if(to!=f)
        dfs(to,x),
        siz[x]+=siz[to],
        cmax(g[x],siz[to]),
        ff|=siz[to]>(n>>1);
    ff|=n-siz[x]>(n>>1);
    if(!ff)rt=x;
}
typedef long long ll;
ll c1[N],c2[N],ans;
bool z[N];int u,v;
void upd(ll*s,int x,int v){
    for(int i=x+1;i<=n+1;i+=i&-i)s[i]+=v;
}
ll qry(ll*s,int x){
    ll res=0;
    for(int i=x+1;i;i-=i&-i)res+=s[i];
    return res;
}
ll qry(ll*s,int l,int r){return qry(s,r)-qry(s,l-1);}
void work(int x,int f){
    upd(c1,siz[f],-1),upd(c1,n-siz[x],1);
    if(x!=rt)
        ans+=x*qry(c1,n-2*siz[x],n-2*g[x]),
        ans+=x*qry(c2,n-2*siz[x],n-2*g[x]),
        ans+=(siz[x]<=n-2*siz[(z[x]|=z[f])?v:u])?rt:0;
    upd(c2,siz[x],1);
    fl(i,x)if(to!=f)work(to,x);
    upd(c1,siz[f],1),upd(c1,n-siz[x],-1);
    if(x!=rt)
        ans-=x*qry(c2,n-2*siz[x],n-2*g[x]);
}
void solve(){
    cnt=0;memset(head,0,sizeof head);
    scanf("%d",&n);
    for(int i=1,x,y;i<n;++i)
        scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1,0),dfs(rt,0);
    ans=u=v=0;
    fl(i,rt)if(siz[to]>siz[v]&&siz[v=to]>siz[u])u^=v^=u^=v;
    memset(c1,0,sizeof c1),memset(c2,0,sizeof c2);
    for(int i=0;i<=n;++i)upd(c1,siz[i],1),z[i]=0;
    z[u]=1;
    work(rt,0);
    printf("%lld\n",ans);
}
int main(){
    for(scanf("%d",&T);T--;)solve();
}
LG 5666 树的重心
comment评论
Search
search