Codeforces #359 D. Kay and Snowflake

正文索引 [隐藏]

传送门:http://codeforces.com/contest/686/problem/D

题目大意

给定 n , q 表示在一棵大小为 n ,根为 1 的树上有 q 个询问。
接下来一行 n-1 个数 ,表示 2~n 每个节点的父亲。
接下里 q 行每行一个数字 x,表示询问以 x 为根的子数的重心是谁? 树的重心:重心删除后得到的最大子树的节点个数size小于等于子树大小的一半。

题解

预处理出以每一个点为根的子树的重心。
树DP往下处理子树大小和深度,然后对于每一个点从他的儿子的重心一直尝试到它自己,找到的第一个小于子树大小一半的点极为重心。
这样保证每个点处理一次是O(n)的,树DP也是O(n)的。

代码