LOJ6669 Nauuo and Binary Tree 解题笔记

题目来源 LOJ6669 Nauuo and Binary Tree 题意简述 这是一道交互题。 有一棵以 111 为根的二叉树，你可以询问任意两点之间的距离，求出每个点的父亲。 节点数不超过 300030003000 ，你最多可以进行 300003000030000 次询问。 解题思路 观察数据范围可知，本题可以接受 O(n2)O(n^2)O(n2) 的时间复杂度，但关键在于如何降低询问复杂度。 显然，本题需要由浅到深地逐层加入节点，否则就无从下手。 设当前待插入的节点为 xxx 。 又由于本题的树满足二叉树的特殊性质，所以可以考虑 xxx 是去左子树还是右子树。 如果暴力询问 xxx 到左儿子和右儿子的距离，选择走哪一棵子树，最坏询问复杂度为 O(n2)O(n^2)O(n2) ，具体情况如下图。 ..