LOJ6669 Nauuo and Binary Tree 题解

· · 个人记录

题目传送门

简要题意：交互题。对于一个有 n(n\le3000) 个节点的二叉树，其中 1 号节点是根节点，你可以询问至多 30000 次任意两个节点的距离，试确定这棵二叉树的结构。

第一反应要确定每个节点的深度。

这里有一种基于边分治思想的错误做法。

  1. 如果在以 u 为根的子树内只有一个节点（设为 v）的深度为 u 的深度加一，则直接确定 u 只有唯一一个儿子 v，u 子树内除本身以外的所有节点标记为在以 v 为根的子树内，递归处理以 v 为根的子树。
  2. 如果在以 u 为根的子树内有多个节点的深度为 u 的深度加一，则这样的节点恰只有两个，记为 v_1,v_2，询问该子树内除 u,v_1,v_2 三个节点以外的节点与 v_1 的距离，可以由深度确定其他节点在 v_1,v_2 中哪个节点的子树，在递归处理。

这样每个节点大约访问了“深度+子树大小个数”次，时间复杂度 O(n^2)，每次都将子树分成了两部分，貌似可以通过。但是，“每次都将子树分成了两部分”不一定是平均分，在如下的情况中，询问次数是 O(n^2) 的。

   1
  / \
 2   3
    / \
   4   5
      / \
     6  ...

我们反思一下为什么这样询问效率低下。我们询问子树节点与 v_1 的距离时，可能的回答只有两个，如果随便询问两点距离，则可能的回答有 O(n) 个，很明显，我们浪费了许多信息！

看来我们需要一种可能的回答有 O(n) 个的算法。我们可以设计这样的一种算法，当我们确定完每个节点的深度后，实际上我们已经至少确定了这棵树上面两层的结构。假设我们确定了这棵树前面 i 层的结构，考虑确定第 i+1 层的结构。

  1. 取出一个位于第 i+1 层的节点 v，初始设 root 为 1 节点。
  2. 从 root 节点一路往重链走（这里定义重儿子为子孙中第 i 层节点较多的儿子），取出一个位于第 i 层的节点 u，询问与 v 的距离。
  3. 若距离为 1 或 3，直接可以确定 v 的父亲。否则可以确定 u 与 v 的 lca，将 lca 远离 v 的儿子记作 root，容易证明 v 在以 root 为根的子树内，重复第二步。

在第二步中由于我们每次取重儿子选取 u，最坏情况下每次也可以缩小至少一半的父亲可能，第 i 层的节点最多有 O(n) 个，则确定每个节点的父亲可以在询问 O(logn) 次内确定。实际询问次数会少于 nlogn 次，可以通过本题。

另：相较于前面的错误方案，本方案能够利用更多询问信息，减少询问次数