RT，通过在“每次线段树合并垃圾回收无用空间”（也就是这里的做法）的做法空间复杂度并不是线性的。

我们构造一棵形如这样的二叉树：
一直这样长到 $n$ 为之。

然后通过对输入边集顺序的构造，使得在 dfs 过程中每次都先访问右子树，这样就会导致在第一次合并操作开始前，所有叶子已经被访问到而插入了值，插入 $\dfrac{n}{2}$ 次那么空间直接 $\mathcal{O}(n\log n)$，然后就爆了。

附一个输入数据生成器：

#include<bits/stdc++.h>
using namespace std;
const int n=1000000;
int main()
{
	cout<<n<<"\n";
	int m=n-1;
	int now=1,cnt=1;
	while(m)
	{
		cnt++;
		cout<<now<<" "<<cnt<<"\n";
		int nxt=cnt;
		m--;
		if(!m) break ;
		cnt++;
		cout<<now<<" "<<cnt<<"\n";
		now=nxt;
		m--;
	}
}

虽然 CF 题加不了 hack，但是无所谓了（