cf1061f专题

【交互】【随机】Lost Root(CF1061F)

正题 luogu CF1061F 题目大意 给出n和k,现在有一颗n个点的满k叉树,每次查询可以问一个点是否在另外两个点的路径上,让你在 60 × n 60\times n 60×n 次询问内得到根节点 解题思路 因为是满k叉数,可以先得到深度dep 每次随机找两个点,用 n 次查询判断这两个点路径之间的点数,如果为 d e p × 2 − 1 dep\times 2-1