首页 > 其他 > 详细

天天爱跑步——树上差分

时间:2018-10-06 20:13:31      阅读:150      评论:0      收藏:0      [点我收藏+]

先来一道简化版:

关联点 2
? 给出一棵二叉树,每个点有点权 ????
? 如果 ?? 在 ?? 的左(右)子树中,且 ?? 到 ?? 的距离为 ????,则称 ??
为 ?? 的左(右)关联点
? 求每个点的左、右关联点个数
? ?? ≤ 10^6

 

子树内距离根为x深度的点有多少个

不能爆搜。

但是,可以利用dfs的性质,便利完a的子树,才会出来。

所以,可以用一个全局数组记录dep[i]表示深度为i的点出现了几次

进入x,记录dep[dep[x]+va]个数=old,然后把dep[dep[x]]++

回溯的时候,把new-old即可求出答案。

 

天天爱跑步——树上差分

原文:https://www.cnblogs.com/Miracevin/p/9748251.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!