平顶山网站建设电话,sem竞价推广托管,微信ios版下载,北京市建设资格注册中心网站正题
题目链接:https://ac.nowcoder.com/acm/contest/7745/E 题目大意
给出nnn个点的一棵树#xff0c;每个点有一个选择权重aia_iai#xff08;有ai∑i1nai\frac{a_i}{\sum_{i1}^na_i}∑i1naiai的概率被选择#xff09;。
然后有一个序列www。随机选择两次点每个点有一个选择权重aia_iai有ai∑i1nai\frac{a_i}{\sum_{i1}^na_i}∑i1naiai的概率被选择。
然后有一个序列www。随机选择两次点可以相同若它们之间距离为LLL那么困难值为wLw_LwL
求期望困难值。
1≤n≤105,0≤wi≤1081\leq n\leq 10^5,0\leq w_i\leq 10^81≤n≤105,0≤wi≤108 解题思路
设pip_ipi表示选择iii的概率那么就是求 ∑i1n∑j1npipjwdis(i,j)\sum_{i1}^n\sum_{j1}^np_ip_jw_{dis(i,j)}i1∑nj1∑npipjwdis(i,j)
看起来很点分治就上点分治吧
怎么合并两个子树的距离设uiu_iui表示子树111中深度为iii的概率和viv_ivi则表示子树222中的。 那么就有 ans∑i1∑j1uiviwij∑i1wi∑j1ujvi−jans\sum_{i1}\sum_{j1}u_iv_iw_{ij}\sum_{i1}w_{i}\sum_{j1}u_jv_{i-j}ansi1∑j1∑uiviwiji1∑wij1∑ujvi−j 看起来很卷积就上NTT\text{NTT}NTT吧
做起来比较麻烦题解告诉我们可以直接计算整个树的然后再分别减去每个子树内的。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n)
这下一雪我半年前考场调了半天长剖NTT的前耻了 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4e510,P998244353;
struct node{ll to,next;
}a[N1];
ll n,l,ans,root,num,mx,tot,ls[N],p[N],w[N];
ll r[N],g[N],siz[N],f[N],x[N];
bool v[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void NTT(ll *f,ll op){for(ll i0;il;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pl;p1){ll lenp1,tmppower(3,(P-1)/p);if(op-1)tmppower(tmp,P-2);for(ll k0;kl;kp){ll buf1;for(ll ik;iklen;i){ll ttbuf*f[ilen]%P;f[ilen](f[i]-ttP)%P;f[i](f[i]tt)%P;bufbuf*tmp%P;}}}if(op-1){ll invnpower(l,P-2);for(ll i0;il;i)f[i]f[i]*invn%P;}return;
}
void GetL(ll n){l1;while(ln)l1;for(ll i0;il;i)r[i](r[i1]1)|((i1)?(l1):0);return;
}
void groot(ll x,ll fa){siz[x]1;g[x]0;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa||v[y])continue;groot(y,x);siz[x]siz[y];g[x]max(g[x],siz[y]);}g[x]max(g[x],num-siz[x]);if(g[x]g[root])rootx;return;
}
void calc(ll x,ll fa,ll dep){(f[dep]p[x])%P;mxmax(mx,dep);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa||v[y])continue;calc(y,x,dep1);}return;
}
void del(){for(ll i0;imx;i)f[i]0;mx0;return;
}
void fuc(ll n,ll z){GetL(2*n);for(ll i0;il;i)x[i]f[i];NTT(x,1);for(ll i0;il;i)x[i]x[i]*x[i]%P;NTT(x,-1);for(ll i0;il;i)(ansz*w[i]*x[i]%P)%P;return;
}
void solve(ll x){v[x]1;ll talnum;calc(x,x,0);fuc(mx1,1);del();for(ll ils[x];i;ia[i].next){ll ya[i].to;if(v[y])continue;calc(y,x,1);fuc(mx1,-1);del();}for(ll ils[x];i;ia[i].next){ll ya[i].to;if(v[y])continue;num(siz[y]siz[x])?(tal-siz[x]):siz[y];root0;groot(y,x);solve(root);}return;
}
signed main()
{scanf(%lld,n);ll s0;for(ll i1;in;i)scanf(%lld,p[i]),sp[i];for(ll i1;in;i)p[i]p[i]*power(s,P-2);for(ll i0;in;i)scanf(%lld,w[i]);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}numn;g[0]1e9;groot(1,1);solve(1);printf(%lld\n,(ansP)%P);return 0;
}
