首页 > 其他分享 >CF48G Galaxy Union

CF48G Galaxy Union

时间:2022-11-20 19:25:17浏览次数:86  
标签:sz 环上 Union times fa CF48G Galaxy

CF48G Galaxy Union

给定一棵基环树,求每个点到其他点的最小距离之和。 \(n\leq 2\times 10^5\) 。

对于在环上的点和在树上的点分开处理。设在环上的点集为 \(H\) ,先求出所有在环上的点 \(i\) 到其他点在环上的距离之和 \(ans_i=\sum\limits_{j\in H} dis(i,j)\times sz_j\) ,其中 \(sz_j\) 表示 \(j\) 的树部分大小,可以做到使用双指针断环为链 \(O(n)\) 求出(因为每个点都可以贪心取较小的一半距离)。

然后所有树上的节点 \(p\) 在环上的答案贡献就是 \(ans_i+\sum\limits_{j\in H\&j\neq i}sz_j\times dis(i,p)\) 。

最后要求树内节点的答案,发现就是当以自己为根是的 \(dep\) 之和,于是可以套上一个简单的换根 DP 解决,式子是 \(f_x=f_{fa}-2\times sz_x\times w_{x,fa}+sz_{root}\times w_{x,fa}\) ,其中 \(sz_x\) 为原树内的子树大小, \(root\) 是所属的子树在链上的点, \(w_{x,fa}\) 是边权。

标签:sz,环上,Union,times,fa,CF48G,Galaxy
From: https://www.cnblogs.com/zhouzizhe/p/16909236.html

相关文章

  • [Typescript] 110. Hard - Union to Tuple
    Implementatype, UnionToTuple,thatconvertsauniontoatuple.Asweknow,unionisanunorderedstructure,buttupleisanordered,whichimpliesthatwe......
  • 微信appid、openid、unionid的区别和关联
    来源:https://blog.csdn.net/qq_41990222/article/details/111587331applicationidentification(简称appid)是应用标识OpenID是一个以用户为中心的数字身份识别框架Un......
  • UnionID 机制说明
    如果开发者拥有多个移动应用、网站应用、和公众帐号(包括小程序),可通过UnionID来区分用户的唯一性,因为只要是同一个微信开放平台帐号下的移动应用、网站应用和公众帐号(包括......
  • 在实际应用中联合体union的妙用
    关键字union,又称为联合体、共用体,联合体的声明和结构体类似,但是它的行为方式又和结构体不同,这里的行为方式主要指的是其在内存中的体现,结构体中的成员每一个占据不同的内存......
  • CF1743F Intersection and Union 题解
    更好体验线段的贡献不好统计,考虑统计每一个点在不同情况中的被覆盖次数,那么每个点的被覆盖次数总和即为答案。设\(f_{i,j,0/1}\)表示\(i\)点在扫描到线段\(j\)时是......
  • MySQL union 和 order by 同时使用
    目录一、出现错误的情况二、解决上述问题的两种方法三、案例分析:求解:常见的错误解法(1)使用union和多个orderby不加括号【报错】(2)orderby在union子句中不起作用正......
  • 【Hive】MapJoin限制场景之一(MapJoin Followed by Union)
    举例说明Hive实现MapJoin限制场景之一,MapJoinFollowedbyUnionHive的MapJoin逻辑会有几个限制场景:UnionFollowedbyaMapJoinLateralViewFollowedbyaMapJoin......
  • [Typescript] 91. Hard - Union to Intersection
    Implementtheadvancedutiltype UnionToIntersection<U>ForexampletypeI=Union2Intersection<'foo'|42|true>//expectedtobe'foo'&42&true htt......
  • c语言借助GNU创建对象和嵌套union使用
    #include<stdio.h>#include<stdlib.h>#include<string.h>/**枚举体占用内存*枚举有符号,根据数值分配内存。[1~4]*但是和编译器相关联,目前我看到的都是4by......
  • L - Intersection and Union Gym - 103993L (线段树)
    题意思路思路很巧妙,首先是枚举每个值的贡献,然后找到了规律,下次做题的时候线分析每个题有啥好规律,然后根据规律做题。再就是线段树的这个思路,感觉很巧妙,通过设置每一段的......