5927专题

Auxiliary Set HDU - 5927

点击打开链接 看了题解才会... 之前还一直想用LCA怎么搞... 对于一个非重要点 只要其下至少两颗子树上分别有两个重要点 那这个非重要点一定是他们的LCA 也变成了重要节点 dfs一遍 记录每个节点的直接孩子有几个 记为son[cur] 对于每一个查询 把点按深度从深到浅排序 然后扫一遍 如果当前点的son[cur]==0 那么以当前点为根的子树上已经不存在重要点 其父节点也就少了一个

(HDU 5927)Auxiliary Set 思维题 2016CCPC东北地区大学生程序设计竞赛 - 重现赛

Auxiliary Set Problem Description Given a rooted tree with n vertices, some of the vertices are important. An auxiliary set is a set containing vertices satisfying at least one of the two condition