首页 > 代码库 > 树分治&树链剖分相关题目讨论

树分治&树链剖分相关题目讨论

预备知识

树分治,树链剖分

 

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

树分治&树链剖分相关题目讨论