前言

感谢 zhenjianuo2025 的题解对我的启发。

本题解操作次数为 ${\color{red}2.5}n\log_2 n+\mathcal O(n)$，是目前题解区里面理论操作次数常数的严格最优，虽然实践上根本比不过跑不满的分治，但是我认为该做法比较有意思，故分享之，也算是给省选加 rp 了。

$3n\log_2 n+\mathcal O(n)$ 做法

考虑这个询问能带给我们什么。询问 $U-\{i\}$ 可以推出以重心为根时，$i$ 的子树大小，在排序后可以得到一个拓扑序。

除此之外，这个操作看上去不太好利用。这是因为他返回的是 $\max$ 信息，如果你调用了 $\operatorname{add}(i)$ 发现前后的值没有改变，这个信息就很难主动利用。这启发我们，对于我们真正在意其返回值的 $\operatorname{add}(i)$，要求操作前其值为 $1$，即操作前是一个独立集，我们 $\operatorname{add}(i)$ 可以得到 $i$ 和该独立集之间的边数。

树是一个二分图，可以划分成两个独立集，可以利用上文所述做法。如何得到这个划分？按照求出的拓扑序，依次加入每个点，若加入后还是独立集就保留，否则删去。显然，最终得到的集合就是所有到根的距离为偶数的点集。

现在需要求解询问集合中每个点的父亲（均来自于其补集——答案集合），我选择了二进制。具体的，枚举位 $i$，按拓扑序插入，判断 $fa_j$ 的第 $i$ 位是否为 $1$。可以参考代码理解。

::::success[核心代码]

const int N = 1e4+5;
int sz[N], id[N], flag[N], ans[N], n;

inline bool cmp(int x, int y){return sz[x]<sz[y];}

inline void color(){
	for (int i = 1;i<=n;i++) add(i), id[i] = i;
	for (int i = 1;i<=n;i++) sz[i] = remove(i), add(i);
	for (int i = 1;i<=n;i++) remove(i);
	sort(id+1, id+n+1, cmp);
	for (int j = 1, i;j<=n;j++){
		i = id[j];
		if (add(i)>1) remove(i), flag[i] = 1;
	}
	for (int i = 1;i<=n;i++) if (!flag[i]) remove(i);
}

inline void Do(int t){
	for (int i = 0;(1<<i)<=n;i++){
		for (int _ = 1, j;_<=n;_++){
			j = id[_];
			if (flag[j] == t){
				if (j&(1<<i)) add(j);
			}
			else{
				if (add(j)>1) ans[j] |= (1<<i);
				remove(j);
			}
		}
		for (int j = 1;j<=n;j++) if (flag[j] == t && (j&(1<<i))) remove(j);
	}
}

void solve(int N){
	n = N; color();
	Do(0), Do(1);
	for (int i = 1;i<=n;i++) if (ans[i]) report(ans[i], i);
}

::::

复杂度证明：对于询问集合，每个点会被插入，删除 $\log(n)$ 次，对于答案集合，点 $i$ 会被插入，删除 $\operatorname{popcount}(i)$ 次，总操作次数 $\sum_i\limits 2(\log(n)+\operatorname{popcount}(i))+\mathcal O(n)=3n\log_2 n+\mathcal O(n)$。

$2.5n\log_2 n+\mathcal O(n)$ 做法

考虑优化上述做法。询问集合的次数无法减少。而对于答案集合，有时 $j$ 的第 $i$ 位和 $i-1$ 位都为 $1$，但因为其必须按拓扑序操作，所以必须 $\operatorname{remove}(j)$ 再 $\operatorname{add}(j)$，有些浪费，我们希望这种情况不用操作。考虑让其操作无序。

考虑使用 CF2164G 的套路。得到一个点邻域的总和与度数，进行剥叶子。由于知道一个点邻域的总和，当他的儿子都被删除时，可以知道他的父亲是谁。

度数可以 $\mathcal O(n)$ 问出来。总和显然可以按位做，并且其目前是无序的（先加入答案集合，再尝试询问集合的每个元素）。所以，若 $j$ 的第 $i$ 位与 $i-1$ 位相同，不需要进行任何操作，否则需要进行 $1$ 次操作。可以证明，这样的操作次数是 $0.5n\log_2 n+\mathcal O(n)$ 的。你可以认为每位是随机的，$i$ 和 $i-1$ 相同的概率是 $\frac 1 2$，当然严谨证明也比较显然。所以总操作次数是 $2.5n\log_2 n+\mathcal O(n)$。

上个做法最后 $\operatorname{add}(j)$ 只可能是 $1$ 或者 $2$，而这个做法 $\operatorname{add}(j)$ 可能的值域更大，利用更充分，所以次数更优。

::::success[核心代码]

const int N = 1e4+5;
int sz[N], id[N], flag[N], sum[N], d[N], st[N], n;
queue<int> q;

inline bool cmp(int x, int y){return sz[x]<sz[y];}

inline void color(){
	for (int i = 1;i<=n;i++) add(i), id[i] = i;
	for (int i = 1;i<=n;i++) sz[i] = remove(i), add(i);
	for (int i = 1;i<=n;i++) remove(i);
	sort(id+1, id+n+1, cmp);
	for (int j = 1, i;j<=n;j++){
		i = id[j];
		if (add(i)>1) remove(i), flag[i] = 1;
	}
	for (int i = 1;i<=n;i++) if (!flag[i]) remove(i);
}

inline void Do(int t){
	int New;
	for (int i = 0;(1<<i)<=n;i++){
		for (int j = 1;j<=n;j++){
			if (flag[j] == t){
				New = (j>>i)&1;
				if (New!=st[j]) New ? add(j) : remove(j); // 0.5nlog n
				st[j] = New;
			}
		}
		for (int j = 1;j<=n;j++){
			if (flag[j]!=t) sum[j] += (add(j)-1)<<i, remove(j); // 2nlog n
		}
	}
  // calc degree
	for (int j = 1;j<=n;j++) if (flag[j] == t && !st[j]) add(j);
	for (int j = 1;j<=n;j++) if (flag[j]!=t) d[j] = add(j)-1, remove(j);
	for (int j = 1;j<=n;j++) if (flag[j] == t) remove(j);
}

inline void make_tree(){
	for (int i = 1;i<=n;i++) if (d[i] == 1) q.push(i);
	int u, f;
	while (!q.empty()){
		u = q.front(), q.pop();
		if (u == id[1]) continue;
		f = sum[u], sum[f] -= u, report(u, f);
		if (--d[f] == 1) q.push(f);
	}
}

void solve(int N){
	n = N; color();
	Do(0), Do(1);
	make_tree();
}

::::