[BZOJ3697] 采药人的路径

采药人的药田是一个树状结构,每条路径上都种植着同种药材。采药人以自己对药材独到的见解,对每种药材进行了分类。大致分为两类,一种是阴性的,一种是阳性的。采药人每天都要进行采药活动。他选择的路径是很有讲究的,他认为阴阳平衡是很重要的,所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的,所以他希望他选出的路径中有一个可以作为休息站的节点(不包括起点和终点),满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。

如XHT大佬所说,这是点分治裸题一个。

点分治,则问题就变成求过根满足条件的路径数。

路径上的休息站一定是在起点到根的路径上,或者根到终点的路径上。

如何判断一条从根出发的路径是否包含休息站?只要在dfs中记录下这条路径的和x,同时用个标志数组判断这条路径是否存在前缀和为x的节点。

枚举根节点的每个子树。用f[i][0/1],g[i][0/1]分别表示前面几个子树以及当前子树和为i的路径数目,0和1用于区分路径上是否存在前缀和为i的节点。那么当前子树的贡献就是$$\sum_{i=-d}^d f [i][0] * g [-i][1] + f[i][1] * (g[-i][0] + g[-i][1])$$其中d为当前子树的深度。然后再加上$$f[0][0] * g[0][0] + f[0][1] $$(当前根作为休息点/当前根作为端点的情况)

这样复杂度就为 n log n。

为啥要写博客?调题太痛苦了,这题调了3小时,在XHT帮助下知道是数组开小了,要记录下来,以后少出错。

\(\)

发表评论

电子邮件地址不会被公开。 必填项已用*标注