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

企业建设网站的母的写论文的网站

企业建设网站的母的,写论文的网站,wordpress手机顶部菜单,ios开发者模式2021牛客OI赛前集训营-提高组#xff08;第四场#xff09; 题目大意 有一棵n1n1n1个节点的树#xff0c;根节点为0。给你一个kkk#xff0c;定义集合Si{j∈Z∣max⁡(1,i−k)≤ji}∪{0}S_i\{j\in Z|\max(1,i-k)\leq ji\}\cup\{0\}Si​{j∈Z∣max(1,i−k)≤ji…2021牛客OI赛前集训营-提高组第四场 题目大意 有一棵n1n1n1个节点的树根节点为0。给你一个kkk定义集合Si{j∈Z∣max⁡(1,i−k)≤ji}∪{0}S_i\{j\in Z|\max(1,i-k)\leq ji\}\cup\{0\}Si​{j∈Z∣max(1,i−k)≤ji}∪{0}。 Ai∑j∈Sidis(i,j)2A_i\sum\limits_{j\in S_i}dis(i,j)^2Ai​j∈Si​∑​dis(i,j)2dis(i,j)dis(i,j)dis(i,j)指iii到jjj在树上的距离。求A1,A2,…,AnA_1,A_2,\dots,A_nA1​,A2​,…,An​分别是多少。 题解 令aia_iai​表示iii在树上的深度注意根节点的深度为1。 那么dis(i,j)2(aiaj−2alca)2ai2aj22aiaj−4alcaai−4alcaaj4alca2dis(i,j)^2(a_ia_j-2a_{lca})^2a_i^2a_j^22a_ia_j-4a_{lca}a_i-4a_{lca}a_j4a_{lca}^2dis(i,j)2(ai​aj​−2alca​)2ai2​aj2​2ai​aj​−4alca​ai​−4alca​aj​4alca2​ 我们可以枚举iii用树链剖分来维护jjj的值。 对于ai2a_i^2ai2​可以直接得出。 对于aj2a_j^2aj2​将所有在SiS_iSi​中的jjj求前缀和即可。 对于2aiaj2a_ia_j2ai​aj​对aja_jaj​求前缀和再乘上2ai2a_i2ai​。 对于4alcaai4a_{lca}a_i4alca​ai​对每个SiS_iSi​中的jjj都将jjj到根节点的路径上的点加1然后查询iii到根节点的路径上的对应值的和再乘上4ai4a_i4ai​即可。 对于4alcaaj4a_{lca}a_j4alca​aj​对每个SiS_iSi​中的jjj都将jjj到根节点的路径上的点加aja_jaj​然后查询iii到根节点的路径上的对应值的和再乘上444即可。 对于4alca24a_{lca}^24alca2​对每个SiS_iSi​中的jjj都将jjj到根节点的路径上的点加ak∗2−1a_k*2-1ak​∗2−1kkk表示当前节点然后查询iii到根节点的路径上的对应值的和因为x2135⋯(x∗2−1)x^2135\cdots(x*2-1)x2135⋯(x∗2−1)所以这样求出的就是alca2a_{lca}^2alca2​然后乘444即可。 对于jjj进入集合或离开集合在jjj到根节点的路径上进行区间修改即可。 为什么根节点的深度为1而不为0呢因为只有根节点的深度为1那么每个点到根节点的路径的长度才能等于这个点的深度这样才能更好地实现。 时间复杂度为O(nlog⁡2n)O(n\log^2 n)O(nlog2n)。 code #includebits/stdc.h #define lc k1 #define rc k1|1 using namespace std; int n,k,x,y,tot0,d[500005],l[500005],r[500005],dep[500005],fa[500005],siz[500005],son[500005]; int tp[200005],s[200005],re[200005]; long long ans,hv1[800005],hv2[800005],mx1[800005],mx2[800005],mx3[800005],ly1[800005],ly2[800005],ly3[800005]; void add(int xx,int yy){l[tot]r[xx];d[tot]yy;r[xx]tot; } void dfs1(int u,int f){fa[u]f;dep[u]dep[f]1;siz[u]1;for(int ir[u];i;il[i]){if(d[i]f) continue;dfs1(d[i],u);siz[u]siz[d[i]];if(siz[d[i]]siz[son[u]]) son[u]d[i];} } void dfs2(int u,int f){if(son[u]){tp[son[u]]tp[u];s[son[u]]s[0];re[s[0]]son[u];dfs2(son[u],u);}for(int ir[u];i;il[i]){if(d[i]f||d[i]son[u]) continue;tp[d[i]]d[i];s[d[i]]s[0];re[s[0]]d[i];dfs2(d[i],u);} } void build(int k,int l,int r){if(lr){hv1[k]2ll*dep[re[l]]-1;hv2[k]1ll;return;}int midlr1;build(lc,l,mid);build(rc,mid1,r);hv1[k]hv1[lc]hv1[rc];hv2[k]hv2[lc]hv2[rc]; } void down(int k){mx1[lc]ly1[k]*hv1[lc];ly1[lc]ly1[k];mx2[lc]ly2[k]*hv2[lc];ly2[lc]ly2[k];mx3[lc]ly3[k]*hv2[lc];ly3[lc]ly3[k];mx1[rc]ly1[k]*hv1[rc];ly1[rc]ly1[k];mx2[rc]ly2[k]*hv2[rc];ly2[rc]ly2[k];mx3[rc]ly3[k]*hv2[rc];ly3[rc]ly3[k];ly1[k]ly2[k]ly3[k]0; } void ch(int k,int l,int r,int x,int y,long long t,int u){if(lxry){mx1[k]t*hv1[k];ly1[k]t;mx2[k]t*hv2[k];ly2[k]t;mx3[k]t*dep[u]*hv2[k];ly3[k]t*dep[u];return;}if(ly||rx) return;if(lr) return;if(ly1[k]||ly2[k]||ly3[k]) down(k);int midlr1;if(xmid) ch(lc,l,mid,x,y,t,u);if(ymid) ch(rc,mid1,r,x,y,t,u);mx1[k]mx1[lc]mx1[rc];mx2[k]mx2[lc]mx2[rc];mx3[k]mx3[lc]mx3[rc]; } void find(int k,int l,int r,int x,int y,int u){if(lxry){ans4ll*(mx1[k]-mx2[k]*dep[u]-mx3[k]);return;}if(ly||rx) return;if(lr) return;if(ly1[k]||ly2[k]||ly3[k]) down(k);int midlr1;if(xmid) find(lc,l,mid,x,y,u);if(ymid) find(rc,mid1,r,x,y,u); } void ask(int i){int ti;while(i1){find(1,1,s[0],s[tp[i]],s[i],t);ifa[tp[i]];} } void ins(int i){int ti;while(i1){ch(1,1,s[0],s[tp[i]],s[i],1,t);ifa[tp[i]];} } void del(int i){int ti;while(i1){ch(1,1,s[0],s[tp[i]],s[i],-1,t);ifa[tp[i]];} } int main() {scanf(%d%d,n,k);n;for(int i1;in;i){scanf(%d%d,x,y);x;y;add(x,y);add(y,x);}dfs1(1,0);s[1]s[0];re[s[0]]1;tp[1]1;dfs2(1,0);build(1,1,s[0]);long long sum10,sum20;for(int i2,vt,vk2;in;i){vtmax(2,i-k);while(vkvt){sum1-1ll*dep[vk]*dep[vk];sum2-1ll*dep[vk];del(vk);vk;}ans1ll*(dep[i]-1)*(dep[i]-1)1ll*(i-vt)*dep[i]*dep[i]sum12ll*dep[i]*sum2;ask(i);printf(%lld\n,ans);sum11ll*dep[i]*dep[i];sum21ll*dep[i];ins(i);}return 0; }
http://www.dnsts.com.cn/news/22845.html

相关文章:

  • 工信部2017网站备案wordpress采集淘宝 插件
  • 伍佰亿网站怎么做长治做网站哪家好
  • 成品网站 修改首页网站建设加关键词是什么意思
  • 株洲网站seo优化价格云搜索app下载
  • dw做网站需要数据库么wordpress用的php代码编辑器
  • 网站的服务器和空间六安哪家公司做网站好
  • 济南建设银行网站做竞价网站服务器多少钱
  • 做汽车网站开题报告的意义天津建行网站
  • .net网站做增删改免费的网站免安装
  • 广告软文是什么意思宁波seo网络推广咨询价格
  • 珠海企业网站建设报价成都公司注册费用
  • 林州企业网站建设wordpress 开启多用户
  • 商城网站建设制作注册的空间网站
  • 某企业网站网页设计模板中国建筑协会证书查询
  • centos7 wordpress网站saas网络推广平台
  • 视频在线网站免费观看html5购物网站
  • 开网站需要租用机房服务器价格北京网站备案负责人变更
  • 网站建设与管理计划书seo 怎么建设网站外链
  • 黄页88网站动态h5网站开发
  • 做二手网站有哪些网站纯色背景图怎么做
  • 正规的环保行业网站开发车网站建设策划
  • 戴南做网站linux下用python做网站
  • wordpress 重定向函数成都优化网站建设
  • 网站建设岗位有哪些关于做美食的网站
  • 外贸企业网站制作做网站创业
  • wordpress网站无法登陆广州网站建设怎么样
  • 利用微博网站做淘客四川建设厅网站复查中
  • ac域名的网站有啥不同湖南株洲建设局网站
  • 在东营怎么建网站数商云电子商务网站建设
  • 上海公司网站建设价格自己电脑做服务器上传网站 需要备案吗