首页 > 代码库 > 树分治&树链剖分相关题目讨论
树分治&树链剖分相关题目讨论
预备知识
树分治,树链剖分
poj1741
?一棵有n个节点的树,节点之间的边有长度。方方方想知道,有多少个点对距离不超过m
题解
点分治模板题。详见我早上写的http://www.cnblogs.com/chouti/p/5836926.html
OrzFang Ⅸ
?有一棵n个点,边长为1的树,他要在树上选择一个大小为m的点集,使得这m个点两两距离相等。
方方方想知道这么做的方案数对998244353取模后的结果。
题解
首先肯定有一个中心点,使得这个点到m个点距离相等
那么枚举这个中心点,枚举距离,注意一个子树最多贡献一个点在点集,类似背包的统计方式合并一下。复杂度目测是大概
OrzFang X
?方方方有一棵n个点的树,每个点点权初始为0。你需要维护m个操作,每个操作为路径加,子树加,路径求和或子树求和。
题解
这题树剖肯定能做,做法类似NOI2015D1T2软件包啥的
每条重链用个线段树
子树修改视作修改一段编号连续的重链‘
路径修改就是修改和路径相交的重链
事实上,子树修改-路径求和这种可以不用树剖,对dfs序建线段树可以更好的解决
OrzFang XI
?方方方有一棵n个点,边长为1的树。他想知道,有多少个点对距离为质数。
题解
codechef PRIMEDST
类似poj1741的点分治,合并递归的结果的时候套上FFT
树分治&树链剖分相关题目讨论
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。