[Gym 101234D] Forest Game 简要题解

Statement

给定一棵 \(n\) 个点的树，每次从还活着的节点中随机选出一个点，把计数器加上其所在的树的大小并把这个点以及与之相连的边删除，求整棵树都被干掉时计数器上数字的期望。

\(n\leq 10^5\)

Solution

思路不难非常想，调代码过于恶心

考虑设 \(a_i\) 表示 \(i\) 的贡献的期望，也就是选 \(i\) 时所在树的大小，那么有：

\[a_i=\sum_j \frac1{\text{dist}(i,j)+1} \]

所以答案就变成了

\[ans=E(\sum_{i=1}^n a_i)=\sum_{i=1}^nE(a_i)=\sum_{i=1}^n\sum_j\frac1{\text{dist}(i,j)+1} \]

显然可以直接 \(O(n^2)\) 暴力求解，考虑优化

发现问题即是在求树上点对信息，考虑淀粉质维护

对于当前分治中心的每棵子树，设生成函数 \(F(x)=\sum cnt_ix^i\) 其中 \(cnt_i\) 表示到分治中心距离 \(i\) 的点的数量，卷一卷就可以了，时间复杂度 \(O(nlog^2n)\)

Code

人调傻了...

#include
#define int long long
using namespace std;
const int N = 4e5+5;
const int mod = 1e9+7;
const double pi = acos(-1.0);

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int s=0,w=1; char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int ksm(int a,int b){
    int res=1;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)res=res*a%mod;
    return res;
}

struct FFT{
    struct cplx{
        double x,y;
        cplx(double x=0,double y=0):x(x),y(y){}
        cplx operator+(const cplx&rhs)const{return cplx(x+rhs.x,y+rhs.y);}
        cplx operator-(const cplx&rhs)const{return cplx(x-rhs.x,y-rhs.y);}
        cplx operator*(const cplx&rhs)const{return cplx(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x);}
    }a[N<<1];
    int rev[N<<1],n;
    void init(int len){
        for(n=1;n>1]>>1)|((i&1)?(n>>1):0);
    }
    void work(cplx *a,int op){
        for(int i=0;iEdge[N];
int n,rt,mx1,mx2,as;
bool vis[N];

void getrt(int u,int fath,int all){
    siz[u]=1,mxp[u]=0;
    for(auto v:Edge[u])if(v!=fath&&!vis[v])
        getrt(v,u,all),siz[u]+=siz[v],mxp[u]=max(mxp[u],siz[v]);
    mxp[u]=max(mxp[u],all-siz[u]);
    if(mxp[u]