Thanks to ToxicPie9 for proofreading and emotional support.

Recently, I was thinking about JOISC 2025 Space Thief. And there is a part where you need to do divide and conquer on a tree, where you need to split the edges of the tree into two components where the edges are both connected.

Basically, we consider an interactive problem on a tree where there is a hidden edge. We are allowed to ask queries of the form $$$(v,N_v)$$$ where $$$v$$$ is a vertex of the tree and $$$N_v$$$ is a set of neighbouring edges of $$$v$$$. Then the query returns to us whether the hidden edge is in the subtree of one of $$$N_v$$$ when we root the tree at $$$v$$$.

We maintain a set of edges that the hidden edge can be in. In each query, we try to split the set of edges into two parts and ask a query to separate them.

In the worst case, we replace the set of edges by the larger component.

Let $$$R$$$ be the maximum ratio of the larger component.

In this blog by maomao90 and the last section of this blog by errorgorn (yes I am citing myself, deal with it), it was shown that $$$R \lt \frac{2}{3}$$$. And it is quite clear that this limit is tight when we consider a node with $$$3$$$ children each of size roughly $$$\frac{n}{3}$$$.

But a natural question to ask is about the amortized lower bound $$$\tilde R$$$.

In this comment by lrvideckis, it was shown that $$$\tilde R \gt \frac{1}{\sqrt{3}}$$$ amortized.

More confusingly, in funnyhat on a Singapore local judge, it was claimed in the editorial that $$$\tilde R \lt \frac{1}{\sqrt{3}}$$$. I was in the editorial session for that problem. The claim seemed shaky but I did not think too much about it.

But now that I thought about it again, I think that $$$\tilde R \lt \frac{1}{\sqrt{3}}$$$ is wrong because I believe I have a construction for which $$$\tilde R \gt \frac{1}{\varphi}$$$.

Because I know that opening a calculator is annoying, I will write that $$$\frac{3}{2}=1.5$$$, $$$\varphi \approx 1.618$$$ and $$$\sqrt{3} \approx 1.732$$$.

Motivation

The reason why a full ternary tree gives us such a low bound on $$$\tilde R$$$ is because the value of $$$R$$$ at each step alternates between $$$\frac{2}{3}$$$ and $$$\frac{1}{2}$$$.

Suppose the current node has $$$3$$$ children of sizes $$$a\le b\le c$$$. Then after two moves, we can always guarantee that our search space is at most size $$$b$$$. To make $$$b$$$ as large as possible it is clearly best to make $$$b=c$$$.

Now suppose the current node has $$$3$$$ children $$$A,B_1,B_2$$$ of sizes $$$a,b,b$$$ where $$$a\le b$$$.

Then after one move, we reduce to a case where we our search space is $$$A \cup B_1$$$, $$$A \cup B_2$$$ or $$$B_1 \cup B_2$$$. In the last case, we can clearly split the search space exactly in half the next move.

So we should focus on the first two cases where the search size is $$$a+b$$$. To construct the worst case we can simply make $$$B_1=B_2$$$.

We want $$$B_1$$$ to split into two subtrees such that we create a similar situation where the centroid of $$$A \cup B_1$$$ has $$$3$$$ children of sizes $$$c,d,d$$$ where $$$c\le d$$$. Here $$$a=d$$$ and $$$b=c + d$$$.

So we can set up the equations $$$\frac{a}{b} = \frac{c}{d}$$$, $$$a=d$$$ and $$$b=c+d$$$ to obtain $$$\frac{d}{c+d} = \frac{c}{d}$$$ which simplifies into $$$x^2+x-1=0$$$ where $$$x = \frac{c}{d}=\frac{\sqrt 5-1}{2} = \frac{1}{\varphi}$$$.

So if you reduce the search space into size $$$a + b$$$, you get $$$\tilde R = \frac{1+\varphi}{1+2\varphi} = \frac{1}{\varphi}$$$ and if you reduce the search into size $$$b + b$$$ and then $$$b$$$, you get $$$\tilde R = \sqrt{\frac{\varphi}{1+2\varphi}} = \frac{1}{\varphi}$$$.

But honestly, I'm not really sure how to prove that there is no better strategy given such a test case. But I'm quite convinced that this test case probably gives us $$$\tilde R \gt \frac{1}{\varphi}$$$.

Explicit Construction

Knowing this, it should not be too hard to explicitly construct a general case tree for this pattern.

It will be related to Fibonacci numbers.

Let $$$F$$$ be a family of trees where the number of vertices in $$$F_i$$$ is approximately the $$$i$$$-th Fibonacci number.

$$$F_0$$$ is the empty tree and $$$F_1$$$ is a single node.

$$$F_i$$$ is defined recursively by joining an additional node to the centroids of $$$F_{i-1}$$$ and $$$F_{i-2}$$$.

In the above image, centroids are colored in red.

Well, $$$|F_i| = |F_{i-1}| + |F_{i-2}| + 1$$$ it is not really the Fibonacci sequence.

The first few values of $$$|F_i|$$$ is $$$0,1,2,4,7,12,20,33,\ldots$$$ which is like Fibonacci numbers $$$-1$$$.

Does it really break funnyhat?

Yes, I managed to make the author's AC code use $$$23$$$ queries (where 22 gets the full score).

Note that I had to change the definition of $$$F_i$$$ a bit so that $$$F_0$$$ is now a single node instead of an empty tree. This is because now $$$F_{23}$$$ has about $$$0.93 \cdot 10^5$$$ nodes which squeezes better in the constraints of the problem. The original construction above was only able to force $$$22$$$ queries.

#include <bits/stdc++.h>
using namespace std;

vector<int> v[30];

int n;
int ans[100005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);

	v[0]={0};
	v[1]={1};

	for (int x=2;x<30;x++){
		for (auto it:v[x-2]) v[x].push_back(it);
		v[x].push_back(x);
		for (auto it:v[x-1]) v[x].push_back(it);
	}

	int k=0;
	while (v[k+1].size()<=100000) k++;

	int cnt=1;
	for (int val=0;val<=30;val++){
		for (int x=0;x<v[k].size();x++){
			if (v[k][x]==val){
				ans[x]=cnt++;
			}
		}
	}

	cout<<3<<" "<<v[k].size()<<" "<<v[k].size()-2<<endl;
	for (int x=0;x<v[k].size();x++) cout<<ans[x]<<" "; cout<<endl;
}

#include <bits/stdc++.h>
using namespace std;
#include "funnyhat.h"
vector<int> adj[100005];
int rt,par[100005],tsz;
int alive[100005],sz[100005];
void dfssize(int x){
	sz[x]=1;
	for(int i:adj[x]){
		if(!alive[i]) continue;
		dfssize(i);
		sz[x]+=sz[i];
	}
}
int findcent(int x){
	for(int i:adj[x]){
		if(!alive[i]) continue;
		if(sz[i]*2>tsz) return findcent(i);
	}
	return x;
}
int find_hat(int n, vector<int> arr) {
	vector<int> mono;
	int l[n],r[n];
	for(int i=0; i<n; i++){
		while(!mono.empty()&&arr[mono.back()]<arr[i]){
			r[mono.back()]=i;
			mono.pop_back();
		}
		if(mono.empty()) l[i]=-1;
		else l[i]=mono.back();
		mono.push_back(i);
	}
	while(!mono.empty()){
		r[mono.back()]=-1;
		mono.pop_back();
	}
	for(int i=0; i<n; i++){
		if(l[i]==-1&&r[i]==-1) rt=i,par[i]=-1;
		else{
			if(l[i]==-1) par[i]=r[i];
			else if(r[i]==-1) par[i]=l[i];
			else if(arr[l[i]]<arr[r[i]]) par[i]=l[i];
			else par[i]=r[i];
			adj[par[i]].push_back(i);
		}
	}
	tsz=n;
	for(int i=0; i<n; i++) alive[i]=1;
	while(tsz>1){
		dfssize(rt);
		int x=findcent(rt);
		vector<pair<int,int> > srt;
		srt.push_back({tsz-sz[x],-1});
		for(int i=0; i<(int)adj[x].size(); i++){
			if(!alive[adj[x][i]]) continue;
			srt.push_back({sz[adj[x][i]],i});
		}
		sort(srt.begin(),srt.end(),greater<pair<int,int> >());
		if(srt[0].second==-1){
			if(see_hat(x)){
				tsz=sz[x];
				rt=x;
				continue;
			}
			else{
				alive[x]=0;
				tsz-=sz[x];
				continue;
			}
		}
		else{
			int nd=adj[x][srt[0].second];
			if(see_hat(nd)){
				tsz=sz[nd];
				rt=nd;
				continue;
			}
			else{
				alive[nd]=0;
				tsz-=sz[nd];
				continue;
			}
		}
	}
	return rt;
}

You can compile the author's solution with the additional files provided in the problem's attachments to verify that it does indeed use $$$23$$$ queries.

Open Problems

(**Open Problem 1**) How to prove that $$$\tilde R \gt \frac{1}{\varphi}$$$ actually holds for this Fibonacci tree? SOLVED

jeroenodb told me the proof that $$$\tilde R \gt \frac{1}{\varphi}$$$. He has given me permission to write it here.

Let $$$C(T)$$$ denote the minimum number of queries we require to solve tree $$$T$$$.

We make two observations:

1. If there is a node $$$x$$$ of degree $$$2$$$ in the tree connected to vertices $$$a$$$ and $$$b$$$, we can make a new tree $$$T'$$$ where $$$x$$$ is deleted and we add an edge between $$$a$$$ and $$$b$$$. Then $$$C(T') \leq C(T)$$$.
2. If $$$T'$$$ is any connect subgraph of tree $$$T$$$, then $$$C(T') \leq C(T)$$$.

Then we will prove that $$$C(F_i) \geq i-2$$$ by induction, to show that indeed $$$\tilde R \geq \frac{1}{\varphi}$$$. For $$$i \leq 2$$$, the claim is clearly true.

The graph of $$$F_i$$$ looks like this.

By case work, we can prove that we can force a recursion into a superset of one of the graphs $$$X_1 \cup a \cup b \cup Y$$$, $$$X_2 \cup b \cup Y$$$ and $$$X_1 \cup a \cup b \cup X_2$$$.

The case work is if $$$v$$$ is chosen to be not $$$b$$$, we will take the subtree that contains $$$b$$$. If $$$v$$$ is $$$b$$$, then we can take the union of two subtrees of children of $$$b$$$.

And because of our previous two observations, we know that $$$C(X_1 \cup a \cup b \cup Y),C(X_2 \cup b \cup Y),C(X_1 \cup a \cup b \cup X_2) \geq C(F_{i-1})$$$.

Therefore, we know that $$$C(F_i) \geq C(F_{i-1}) + 1$$$.

(**Open Problem 2**) Can we improve the bound $$$\frac{1}{\varphi} \lt \tilde R \lt \frac{2}{3}$$$? SOLVED.

Golovanov399 shown in the first comment on the blog that $$$\tilde R \lt \frac{1}{\varphi}$$$.

Conclusion

Because all open problems have been resolved (rather quickly I might add), we actually shown that $$$\tilde R = \frac{1}{\varphi}$$$. Maybe I should have thought about this more before I posted the blog. But I think I really would not have believed that the upper bound of $$$\tilde R$$$ could have been improved.

Time to update all our libraries I guess?