CodeForces – 1305D Kuroni and the Celebration(思维互动题)

题目链接:点击查看 题目大意:给出一个由 n 个点组成的树,现在可以询问 n/2 次(向下取整)LCA,确定根节点是哪个节点 题目分析:因为最多只能求 n/2 次lca,每次需要两个节点作为参数,也就是说每个点我们至多遍历一遍,读完题后没什么思路,队友给我提示说可以参考树上启发式合并的思想,从叶子结点向上不断合并找到根节点,由此我感觉可以根据度来找到叶子结点,每次询问两个叶子结点的LCA,直到存在着某次的LCA等于叶子结点就找到根节点了,因为如果两个叶子结点的LCA不是两者之一的话,那么说明这两个叶子结点必定不可能是根节点,所以直接扔掉就好了,如此往复,从外向内,首先满足特判的点肯定就是根节点