当前位置: 首页 > news >正文

简单的购物网站开发企业网站开发标准

简单的购物网站开发,企业网站开发标准,阿里云虚拟主机多网站吗,凡客网正题 题目大意 nnn个节点的一棵树#xff0c;随机选择一个区间#xff0c;求这个区间的点所构成的虚树的期望权值和。 解题思路 考虑每一条边的贡献#xff0c;定义一边的点为黑点#xff0c;一边的为白点#xff0c;显然包含黑白的区间都会产生贡献。考虑减去没有贡献的…正题 题目大意 nnn个节点的一棵树随机选择一个区间求这个区间的点所构成的虚树的期望权值和。 解题思路 考虑每一条边的贡献定义一边的点为黑点一边的为白点显然包含黑白的区间都会产生贡献。考虑减去没有贡献的也就是对于连续的一段长度为lll的颜色相同的区间会产生贡献n(n1)2\frac{n(n1)}{2}2n(n1)​ 用线段树维护然后合并即可。 时间复杂度O(nlog⁡n)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); }
http://www.huolong8.cn/news/69254/

相关文章:

  • 高明做网站怎么通过贷款网站找做贷款客户
  • 网站名查找wordpress 小清新主题
  • 国内做设计的网站有哪些员工管理系统源码
  • 网站运营与管理的心得体会网站用户管理体系
  • 西安大型网站建设班级网站怎么做ppt
  • 饶平网站建设开发公司工程部管理制度
  • wordpress谷歌字体加载慢重庆seo俱乐部联系方式
  • 站长网网站模板下载wordpress 小工具修改
  • 免费做那个的视频网站好帝国cms添加网站地图
  • 网站建设中 显示网站制作流程 优帮云
  • 网站建设动态网站推广问题
  • 备案成功的网站杭州网络科技设计中心
  • 自助房申请网站wordpress在评论框中加文字
  • 休闲咖啡厅网站开发目标初二信息课网站怎么做
  • 网站开发外贸网网站建设的公司
  • 网站建设哪家好 北京理发培训专业学校
  • 搭建网站需要哪些东西企业服务有哪些内容
  • 十年经验网站开发公司微信主题wordpress
  • 湖北网站建设报价便宜电商网站建设
  • 网站后台上传表格简述网站开发具体流程图
  • 网站wordpress入侵今天广州新闻最新消息
  • 农业推广网站建设无锡建网站
  • 单职业传奇网站wordpress 创建分类
  • 男女做爰视频免费网站平面设计培训班课程
  • dw+如何做自适应网站安徽省建设工程安全协会网站
  • asp网站开发的背景与环境免费招聘模板下载
  • 网站建设价格标准新闻小程序启动失败 错误码
  • 怎样下载网站模版怎么运用区块链做网站
  • 免费网站注册免费创建网站网站内页301重定向
  • 长宁企业网站制作做网站公奇闻司郑州汉狮