题解：CF2222G Statistics on Tree

· · 题解

直接考虑点分治类似，容易转化为统计 \max(a_x,a_y,n-b_x-b_y) ，其中 a 是某点到根路径断开后路径上（不包含根）的最大分量大小，b 是根的这一方向子树的大小。

硬做会带若干个老哥。发现 a_x\le b_x，因此若 a_x\ge n-b_x-b_y 则 2b_x+b_y\ge n，必有 \max(b_x,b_y)\ge\frac{n}{3}，这样的子树只有 O(1) 个。

但是点分治其实也会多带老哥。考虑以重心为根，a,b 变为关于 lca 的信息。发现若 lca 不在第 2 层，则 n-b_x-b_y\ge\frac{n}{2}，因此这就是 max。于是可以先对所有点统计 n-b_x-b_y，再对第 2 层 O(1) 个 \ge\frac{n}{3} 的子树单独统计。

考虑第一部分，即 ans_{n-sz_x-sz_y}\leftarrow sz_xsz_y。考虑将相同项合并暴力做，结合自然根号及 dsu on tree，将重子树单独考虑并考虑轻子树大小和，不难分析出 O(n\log n)。

考虑第二部分，容易转化为 O(1) 次二维数点问题，O(n\log n)。

:::success[点击查看参考代码]

#include<bits/stdc++.h>
#define TIME chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()
#define rep(i,l,r) for(int qwp=(r),i=(l);i<=qwp;i++)
#define per(i,r,l) for(int qwp=(l),i=(r);i>=qwp;i--)
#define pb push_back
#define clr clear
#define SZ(x) (int)((x).size())
#define LB lower_bound
#define fir first
#define sec second
using namespace std;
namespace c0dE1ng{
typedef long long ll;
typedef vector<int> arr;
constexpr int N=1e5+5;
int n;arr g[N];ll ans[N];
int sz[N],rt,rtv;void dfs1(const int u,const int pre){
    sz[u]=1;int t=0;for(auto v:g[u])if(v!=pre)
    dfs1(v,u),sz[u]+=sz[v],t=max(t,sz[v]);
    t=max(t,n-sz[u]);if(t<rtv)rt=u,rtv=t;
}
arr a[N];void dfs2(const int u,const int pre,const int to,int mx){
    for(auto v:g[u])if(v!=pre)dfs2(v,u,to,max(mx,sz[u]-sz[v]));
    mx=max(mx,sz[u]),a[to].pb(mx);
}
map<int,int>cnt;void dfs3(const int u,const int pre){
    arr a;for(auto v:g[u])if(v!=pre)dfs3(v,u),a.pb(sz[v]);
    cnt.clr();for(auto t:a){
        for(auto w:cnt)ans[n-w.fir-t]+=w.sec*1ll*t;
        if(pre)ans[n-t]+=t;cnt[t]+=t;
    }
}
int cc[N];
void slv(){
    cin>>n;rep(i,1,n)g[i].clr();rep(i,1,n-1){int x,y;cin>>x>>y;g[x].pb(y),g[y].pb(x);}
    rtv=n+1,dfs1(1,0),dfs1(rt,0);
    rep(i,1,n-1)ans[i]=0;ans[n]=n;
    for(auto v:g[rt]){
        a[v].clr(),dfs2(v,rt,v,0);
        for(auto t:a[v])ans[max(t,n-sz[v])]++;
    }
    dfs3(rt,0);for(auto v:g[rt])sort(a[v].begin(),a[v].end());
    rep(i,0,SZ(g[rt])-1){
        const int x=g[rt][i];if(sz[x]<n/3)continue;
        rep(_,0,SZ(a[x]))cc[_]=0;
        rep(j,0,SZ(g[rt])-1){
            const int y=g[rt][j];if(y<=x&&sz[y]>=n/3)continue;
            const int t=n-sz[x]-sz[y];ans[t]-=sz[x]*1ll*sz[y]-(LB(a[x].begin(),a[x].end(),t)-a[x].begin())*1ll*(LB(a[y].begin(),a[y].end(),t)-a[y].begin());
            for(auto q:a[y]){
                cc[LB(a[x].begin(),a[x].end(),max(q,t))-a[x].begin()]++;
                if(q>=t)ans[q]+=LB(a[x].begin(),a[x].end(),q)-a[x].begin();
            }
        }
        for(int _=0,sum=0;sum+=cc[_],_<SZ(a[x]);_++)ans[a[x][_]]+=sum;
    }
    rep(i,1,n)cout<<ans[i]<<' ';cout<<'\n';
}
void main(){
    cin.tie(0)->sync_with_stdio(0);
    int T;cin>>T;
    while(T--)slv();
}
}
int main(){
    auto _Tbe=TIME;
    c0dE1ng::main();
    auto _Ted=TIME;
    cerr<<"\nTIME:"<<_Ted-_Tbe<<"ms\n";
    return 0;
}
/*
ulimit -s 1048576
g++ -O2 -std=c++14 -static A.cpp -o %;size %;./% < A.in > A.out
*/

:::