[eJOI2023] Tree Search 题解

· · 题解

看到 35 次询问这个奇怪的限制，如果是二分询问次数不可能放这么松，二分带个常数也跑不过去。于是考虑每次把询问的子树大小缩小到原来的 \frac{2}{3}。

可以采用以下方法：一开始令 r 为根，在不断确定答案的过程中改变 r 并且在之后的询问中仅考虑 r 的子树内的结点。

对于当前 r 的两个儿子，先询问子树大的那个，如果目标结点在它的子树里面并且该子树大小 >\frac{2}{3} 的整棵树（这里“整棵树”仅包含当前可能成为答案的结点，而不是最开始给出的树）的大小，那么不断找这个儿子结点的子树较大的儿子，直到找到一棵大小 \le 整棵树的 \frac{1}{2} 的子树（可以证明它的大小一定不小于整棵树的 \frac{1}{3}，所以可以将树的大小缩小到原来的 \frac{2}{3}）；否则显然就可以将树的大小缩小到原来的 \frac{2}{3}。

上面的过程中可能遇到目标结点不在满足条件的子树里面，那么直接将整棵子树删去是正确的（实现中给该子树的根打上标记即可）。

询问次数 O(\log_{1.5}n)，当 n=10^5 时可以通过 35 次询问限制。

放代码（为原题交互格式，请自行修改为洛谷版本）：

#include "stub.h"
#include<bits/stdc++.h>
using namespace std;
int solve(int n,vector<int> p){
  vector<vector<int> > g(n);
  for(int i=1;i<n;i++)
    g[p[i-1]-1].emplace_back(i);
  vector<bool> b(n);
  vector<int> e(n);
  int r=0;
  function<void(int)> dfs=[&](int u){
    for(int i:g[u])
      if(!b[i])dfs(i),e[u]+=e[i];
  }; // 计算子树大小
  function<int(int)> f=[&](int u){
    vector<int> s;
    for(int i:g[u])
      if(!b[i])s.emplace_back(i);
    if(s.size()>1&&e[s[1]]>e[s[0]])swap(s[0],s[1]);
    for(int i:s){
      if(e[i]<<1<=e[r])return i; // 满足条件
      if(int x=f(i);~x)return x; // 继续找儿子
    }
    return -1;
  }; // 找满足条件的子树
  while(1){
    fill(e.begin(),e.end(),1);
    if(dfs(r);e[r]==1)return r+1;
    if(int x=f(r);ask(x+1))r=x; // 在该子树内
    else b[x]=true; // 在另一棵子树里面
  }
}