中国建设银行网站密码忘了怎么办,网盘做扩大网站服务器,整装公司排名前十强,wordpress和django正题 题目大意 nnn个节点的一棵树#xff0c;随机选择一个区间#xff0c;求这个区间的点所构成的虚树的期望权值和。 解题思路
考虑每一条边的贡献#xff0c;定义一边的点为黑点#xff0c;一边的为白点#xff0c;显然包含黑白的区间都会产生贡献。考虑减去没有贡献的…正题 题目大意
nnn个节点的一棵树随机选择一个区间求这个区间的点所构成的虚树的期望权值和。 解题思路
考虑每一条边的贡献定义一边的点为黑点一边的为白点显然包含黑白的区间都会产生贡献。考虑减去没有贡献的也就是对于连续的一段长度为lll的颜色相同的区间会产生贡献n(n1)2\frac{n(n1)}{2}2n(n1)
用线段树维护然后合并即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510,MN*20,XJQ1e97;
ll f(ll n)
{return n*(n-1)/2;}
struct Seg_Tree{ll cnt,ls[M],rs[M],lb[M],rb[M],lw[M],rw[M],ans[M];void PushUp(ll x,ll L,ll R){ll mid(LR)1;if(!ls[x])ls[x]cnt,lb[cnt]rb[cnt](mid-L1),ans[cnt]f(mid-L1);if(!rs[x])rs[x]cnt,lb[cnt]rb[cnt](R-mid),ans[cnt]f(R-mid);ans[x]ans[ls[x]]ans[rs[x]];ans[x]ans[x]-f(rb[ls[x]])-f(lb[rs[x]])f(rb[ls[x]]lb[rs[x]]);ans[x]ans[x]-f(rw[ls[x]])-f(lw[rs[x]])f(rw[ls[x]]lw[rs[x]]);lb[x](lb[ls[x]]mid-L1)?(lb[ls[x]]lb[rs[x]]):lb[ls[x]];rb[x](rb[rs[x]]R-mid)?(rb[rs[x]]rb[ls[x]]):rb[rs[x]];lw[x](lw[ls[x]]mid-L1)?(lw[ls[x]]lw[rs[x]]):lw[ls[x]];rw[x](rw[rs[x]]R-mid)?(rw[rs[x]]rw[ls[x]]):rw[rs[x]];}void Change(ll x,ll l,ll r,ll pos){if(!x)xcnt;if(lr){lw[x]rw[x]1;return;}ll mid(lr)1;if(posmid)Change(ls[x],l,mid,pos);else Change(rs[x],mid1,r,pos);PushUp(x,l,r);}ll Merge(ll x,ll y,ll l,ll r){if(!x||!y)return xy;if(lb[x]r-l1)return y;if(lb[y]r-l1)return x;ll mid(lr)1;ls[x]Merge(ls[x],ls[y],l,mid);rs[x]Merge(rs[x],rs[y],mid1,r);PushUp(x,l,r);return x;}
}T;
struct node{ll to,next;
}a[N*2];
ll n,tot,ls[N],rt[N],ans;
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
ll power(ll x,ll b){ll ans1;x%XJQ;while(b){if(b1)ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
void dfs(ll x,ll fa){T.Change(rt[x],1,n,x);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);T.Merge(rt[x],rt[y],1,n);}ansf(n)-T.ans[rt[x]];return;
}
int main()
{freopen(communicate.in,r,stdin);freopen(communicate.out,w,stdout);scanf(%lld,n);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}dfs(1,1);ansans*2%XJQ;printf(%lld,ans*power(n*(n1)/2,XJQ-2)%XJQ);
}
