Cptraser/ 十月 24, 2018/ BeforeBuild/ 1 comments

BZOJ3451NORMAL

题目传送门

考虑每个点对的贡献。
对于(x,y),如果x对y有1的贡献(即y在点分树上是x的祖先),那么y一定是x到y路径上第一个被选做分治中心的点。
一条路径上被选择的点概率相等,因此贡献为\frac{1}{dis(x,y)+1}
所以答案就是\sum_{i=1}^n\sum_{j=1}^n\frac{1}{dis(i,j)+1}
原问题就转化为了点分治的基础问题。
点分治,处理出当前点分树上的所有深度。
上面这个东西是一个很舒服的卷积。
FFT即可。

主要是来填一下点分治的坑。

  • 点分治

将原树问题拆分成两个子树问题分治

比如求上面这个东西,你直接FFT的话会出现子树之内重复统计,就要减去子树内的贡献。
类似差分。

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;

char tc(){static char tr[100000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,100000,stdin),A==B)?EOF:*A++;}
void read(int &x){char c;for(;!isdigit(c=tc()););for(x=c-48;isdigit(c=tc());x=(x<<1)+(x<<3)+c-48);}

const int Maxm=130000,Mod=998244353,Maxn=5e4+5;
const double pi=acos(-1.0);

long long Ans;
struct Complex{double x,y;}A[Maxn],W[2][Maxn];
Complex operator +(Complex x,Complex y){return (Complex){x.x+y.x,x.y+y.y};}
Complex operator -(Complex x,Complex y){return (Complex){x.x-y.x,x.y-y.y};}
Complex operator *(Complex x,Complex y){return (Complex){x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x};}
int limit=1,R[Maxm],Ct,Sum[Maxm];
void Pre(void){
    Complex w=(Complex){cos(2.0*pi/limit),sin(2.0*pi/limit)};
    W[0][0].x=W[1][0].x=1;
    for(int i=1;i<limit;i++)W[1][i]=W[1][i-1]*w;
    for(int i=1;i<limit;i++)W[0][i]=W[1][limit-i];
    for(int i=0;i<limit;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(Ct-1));
}
void FFT(Complex *A,int P){
    for(int i=0;i<limit;i++)if(i<R[i])swap(A[i],A[R[i]]);
    for(int i=1;i<limit;i<<=1){
        for(int j=0;j<limit;j+=(i<<1)){
            for(int k=0;k<i;k++){
                Complex x=A[j+k],y=W[P==1][limit/(i<<1)*k]*A[i+j+k];
                A[j+k]=x+y,A[i+j+k]=x-y;
            }
        }
    }
}

int Ksm(int x,int y){
    int res=1;for(;y;y>>=1,x=1ll*x*x%Mod)if(y&1)res=1ll*res*x%Mod;
    return res;
}

int N,Sz[Maxn],Rt,f[Maxn],vis[Maxn],Wt,Dep[Maxn],Nt,At[Maxn],x,y;
int head[Maxn],nxt[Maxn<<1],to[Maxn<<1],Cnt=1;
int Add(int x,int y){
    to[Cnt]=y,nxt[Cnt]=head[x],head[x]=Cnt++;
    to[Cnt]=x,nxt[Cnt]=head[y],head[y]=Cnt++;
}
void Getroot(int Now,int fa){
    Sz[Now]=1,f[Now]=0;
    for(int i=head[Now];i;i=nxt[i]){
        if(to[i]==fa||vis[to[i]])continue;
        Getroot(to[i],Now);
        Sz[Now]+=Sz[to[i]];
        f[Now]=max(f[Now],Sz[to[i]]);
    }
    f[Now]=max(f[Now],Nt-Sz[Now]);
    if(f[Now]<f[Rt])Rt=Now;
}
void Getdeep(int Now,int fa){
    At[++Wt]=Dep[Now];
    for(int i=head[Now];i;i=nxt[i]){
        if(to[i]==fa||vis[to[i]])continue;
        Dep[to[i]]=Dep[Now]+1;
        Getdeep(to[i],Now);
    }
}
void Calc(int P){
    int M=0;Ct=0;
    for(int i=0;i<limit;i++)A[i].x=A[i].y=0;
    for(int i=1;i<=Wt;i++)M=max(M,At[i]),A[At[i]].x++;
    for(limit=1,M<<=1;limit<=M;limit<<=1,Ct++);
    Pre(),FFT(A,1);for(int i=0;i<limit;i++)A[i]=A[i]*A[i];
    FFT(A,-1);for(int i=0;i<=M;i++)Sum[i]+=P*(int)(A[i].x/limit+0.5);
}
void dfs(int Now){
    Wt=Dep[Now]=0,vis[Now]=1,Getdeep(Now,0);Calc(1);
    for(int i=head[Now];i;i=nxt[i]){
        if(vis[to[i]])continue;
        Dep[Now]=1;Wt=0,Getdeep(to[i],0),Calc(-1);
        Nt=Sz[to[i]],Rt=0,Getroot(to[i],0);
        dfs(Rt);
    }
}
int main()
{
    read(N);register int i;
    for(i=1;i<N;i++)read(x),read(y),Add(x,y);
    f[0]=2e9,Nt=N,Getroot(1,0),dfs(Rt);
    for(i=0;i<=N;i++)
        (Ans+=1ll*Sum[i]*Ksm(i+1,Mod-2)%Mod)%=Mod;
    printf("%lld\n",Ans);
}
Share this Post

1 Comment

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*