HDU 4836 The Query on the Tree

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4836

题解

我们不动树的形态,而直接判断根和查询点的位置关系。
首先如果,根和查询点重合,直接求整个树的和。
如果根的深度<查询点的深度 或者 ,那么直接查询这个点所在子树和即可。
如果根的深度>查询点且 根向上跳深度差那么多步刚好调到查询点,那么只需要求整颗树的和-根所在的查询点孩子的那片子树的和即可。
如果都不满足,那么直接查询这个点所在子树和即可。
只需要DFS序+倍增父亲节点即可。

代码