bzoj 3697 采药人的路径

Posted by

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=3697

题解

点分治:统计过当前根节点满足条件的路径数;

统计每个子树中根到每个节点的路径权值和,将权值和为\(x\)的路径的数目记录在\(f[x][0/1],g[x][0/1]\)中,其中\(f\)记录当前子树的信息,\(g\)记录之前遍历过的子树的信息,\(0,1\)分别记录是否存在休息站;

至于如何记录休息站,可以用桶记录当前路径权值的各前缀来判断;

当前子树的贡献即为\(f[0][0]\times g[0][0]+\sum_{i=-mxdep}^{mxdep} f[i][0]\times g[-i][1]+f[i][1]\times g[-i][0]+f[i][1]\times g[-i][1]\),\(mxdep\)为当前子树的最大深度。

代码

Leave a Reply

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