bzoj 1086: [SCOI2005]王室联邦 树分块

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1086


这道题可以说是手把手教你树分块要怎样分

进行dfs,每访问到一个点就进栈,当发现某个子树的点加到一起大于等于B后,就把它们算进一个块,然后不断弹栈,直到遇到当前点(有点像tarjan)

这样可以保证dfs一遍之后所有的块内的点不超过2B,然后剩下的那些无论加到哪个块中都是合法的

 

发表评论