• Tree(点分治)

    Tree(点分治)

    Tree对问题的分析设计过程该题要求求出树上路径长度$\leqK$的路径总数,为点分治经典题目程序中用到的数据机构和算法程序使用点分治实现,点分治的思想为将一颗树通过重心分割成多棵树来分治求解。即答案=路径通过重心的合法数目+子树答案。求解路径通过重心的合法数目可以通过容斥原理在$O(n\logn)$的时间内得出,可以证明,在用重心进行分割的前提下,时间复杂度为$O(n\log^2n)$程序的运行情况该程序提交了两次才通过,具体情...

    02017年10月29日33点分治
  • HNOI2015 Day 2题解

    HNOI2015 Day 2题解

    昨天做了HNOIday2,感觉好像还是可做的,想当年什么splay还是高级算法,现在点剖什么就老考了简直丧病,虽然第二题还没写那就先当下嘴巴选手吧==T1:[HNOI2015]落忆枫音描述:http://www.lydsy.com/JudgeOnline/problem.php?id=4011这道题还是挺神奇的,首先如果是个DAG的话我们可以把所有点的入度相乘就得到答案。那么现在加上了一条边x->y,也就是说答案=原来的答案+用上这条边的答案,我们可以发现,如果我们把...

  • BZOJ 3924: [Zjoi2015]幻想乡战略游戏(动态点分治)

    BZOJ 3924: [Zjoi2015]幻想乡战略游戏(动态点分治)

    这种动态点分治嘛,GDKOI时听打到了,也有同学讲到了,所以印象比较深刻也就想出来了,然后就在实现方面卡了好久==不得不说CLJ说得真的太简单了,实现方面根本没提。首先我们可以先用树分治构建出这棵树的分治树,也就是把这棵树的重心作为根节点然后子树为他的子树的重心这样递归下去,然后每个节点存的是其子树的信息。对于每个节点我们保存这个子树的dv的总和已经把该节点作为点的答案值这样对于修改能在logn的时间内解...

    02015年4月12日118点分治,老的存档