专业网站开发报价,网站流量分析表,财务记账网站开发,网页版微博题意#xff1a;随机分治中心点分治的期望操作次数 n≤3104n\leq 3\times 10^4n≤3104
即求点分树的 siz 之和的期望
即祖孙关系对数期望
考虑一有序点对 (u,v)(u,v)(u,v)#xff0c;uuu 在点分树上是 vvv 祖先当且仅当 uuu 是 u∼vu\sim vu∼v 路径上第一个被选为分治中心…题意随机分治中心点分治的期望操作次数
n≤3×104n\leq 3\times 10^4n≤3×104
即求点分树的 siz 之和的期望
即祖孙关系对数期望
考虑一有序点对 (u,v)(u,v)(u,v)uuu 在点分树上是 vvv 祖先当且仅当 uuu 是 u∼vu\sim vu∼v 路径上第一个被选为分治中心的并且选择路径外的点是不影响的,所以概率为 1dist(u,v)1\dfrac 1{\operatorname{dist}(u,v)1}dist(u,v)11
由期望线性性答案为
∑i1n∑j1n1dist(i,j)1\sum_{i1}^n\sum_{j1}^{n}\frac 1{\operatorname{dist}(i,j)1}i1∑nj1∑ndist(i,j)11
相当于是求距离为 0∼n−10\sim n-10∼n−1 的点对数量考虑点分治
计算当前答案时发现是个卷积形式使用 NTT 优化
算出整个连通块的答案然后容斥掉在同一个子树中的
因为深度是不会超过大小的所以复杂度为 O(nlog2n)O(n\log ^2n)O(nlog2n)
#include iostream
#include cstdio
#include cstring
#include cctype
#include vector
#define MAXN 65536
using namespace std;
const int MOD998244353;
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
typedef long long ll;
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ans(ll)ans*a%MOD;a(ll)a*a%MOD,p1;}return ans;
}
#define inv(x) qpow(x,MOD-2)
int rt[2][24];
int l,lim,r[MAXN];
inline void init(){lim1l;for (int i0;ilim;i) r[i](r[i1]1)|((i1)(l-1));}
inline void NTT(int* a,int type)
{for (int i0;ilim;i) if (ir[i]) swap(a[i],a[r[i]]);for (int L0;Ll;L){int mid1L,lenmid1;ll Wnrt[type][L1];for (int s0;slim;slen)for (int k0,w1;kmid;k,ww*Wn%MOD){int xa[sk],y(ll)w*a[smidk]%MOD;a[sk]add(x,y),a[smidk]dec(x,y);}}if (type){int tinv(lim);for (int i0;ilim;i) a[i](ll)a[i]*t%MOD;}
}
inline double calc(int* a,int n)
{double ans0;for (l0;(1l)(n1);l);init(),NTT(a,0);for (int i0;ilim;i) a[i](ll)a[i]*a[i]%MOD;NTT(a,1);for (int i0;ilim;i){ans(double)a[i]/(i1);a[i]0;}return ans;
}
vectorint e[MAXN];
double ans;
bool vis[MAXN];
int siz[MAXN],maxp[MAXN]{0x7fffffff},Rt;
int a[MAXN];
void findrt(int u,int f,int sum)
{siz[u]1,maxp[u]0;for (int i0;i(int)e[u].size();i)if (e[u][i]!f!vis[e[u][i]]){findrt(e[u][i],u,sum);siz[u]siz[e[u][i]];maxp[u]max(maxp[u],siz[e[u][i]]);}maxp[u]max(maxp[u],sum-siz[u]);if (maxp[u]maxp[Rt]) Rtu;
}
int dfs(int u,int f,int dep)
{siz[u]1,a[dep];int mxdep;for (int i0;i(int)e[u].size();i)if (e[u][i]!f!vis[e[u][i]]){mxmax(mx,dfs(e[u][i],u,dep1));siz[u]siz[e[u][i]];}return mx;
}
inline void calc()
{anscalc(a,dfs(Rt,0,0));for (int i0;i(int)e[Rt].size();i)if (!vis[e[Rt][i]])ans-calc(a,dfs(e[Rt][i],0,1));
}
void solve()
{int uRt;vis[u]1;calc();for (int i0;i(int)e[u].size();i)if (!vis[e[u][i]]){int ve[u][i];Rt0,findrt(v,0,siz[v]);solve();}
}
int main()
{rt[0][23]qpow(3,119),rt[1][23]inv(rt[0][23]);for (int i22;i0;i--){rt[0][i](ll)rt[0][i1]*rt[0][i1]%MOD;rt[1][i](ll)rt[1][i1]*rt[1][i1]%MOD;}int n;scanf(%d,n);for (int i1;in;i){int u,v;scanf(%d%d,u,v);u,v;e[u].push_back(v),e[v].push_back(u);}findrt(1,0,n);solve();printf(%.4f\n,ans);return 0;
}
