自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 22:44:58，当前版本为作者最后更新于2024-08-18 07:52:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Problem Link

题目大意

给定一棵 $n$ 个点的树，你可以进行 $5\times 10^5$ 次询问：每次询问给定三个点 $x,y,z$，如果三个点不在一条链上，返回 $0$，否则返回链中间的节点。请求出树的重心。

数据范围：$n\le 3\times 10^4$。

思路分析

先考虑链的情况，首先求出区间的两个端点是很容易的，维护 $l,r$，每次加入 $i$ 后把 $l,r$ 变成 $i,l,r$ 中不等于 $f(i,l,r)$ 的两个点即可。

然后可以考虑随机二分，每次随机找一个点 $u$，然后 $\mathcal O(n)$ 判断每个点在 $[l,u]$ 还是 $[u,r]$ 上，只需求判断 $f(l,i,u)=u$ 是否成立，然后递归较大的一边即可。

事实上，随机二分的过程中，每次期望删掉 $\dfrac 14$ 的点，那么询问的总点数期望为 $\mathcal O(n)$ 级别。

然后考虑原问题。

尝试把原问题转成链的情况，我们可以随机两个点 $l,r$，然后在 $l\to r$ 的链上找重心，由于重心的每个子树大小 $\le\dfrac n2$，因此重心在 $l\to r$ 的概率不小于 $\dfrac 12$，期望随机次数为 $\mathcal O(1)$ 级别。

如果重心在这条链上，那么链上该点左侧、右侧的点的子树大小和均 $\le \dfrac n2$，相当于在链上求带权中位数，那么就可以把树上问题转成链上问题。

依然考虑在 $l\to r$ 的链上随机一个点，但此时重心不在链的中点处，因此删掉点的数量没有保证。

如果进行带权二分，即在 $n$ 个点中随机一个，求出该点在链上哪个点的子树内，此时每次删掉的点期望就有保证了。

设随机出的点是 $v$，对应链上节点为 $u$，那么 $f(u,i,v)=i$ 时令 $u\gets i$，不断进行此操作即可。

然后求出 $u$ 在链上的左右部分 $L,R$，然后求 $L,R,u$ 的子树，这些都是容易求出的，递归时判断 $|L|,|R|\le\dfrac n2$ 是否成立即可，如果不成立则递归链为 $L/R$。

这样做，询问总点数的期望为依然为 $\mathcal O(n)$ 级别。

最后我们要判断求出的点是否是重心。

考虑把 $u$ 删去后形成的若干子树，如果 $u$ 不是重心，说明这些子树的大小中存在绝对众数，可以考虑摩尔投票法，我们只要快速判断两个点是否属于 $u$ 的同一个子树，这是简单的。

为了优化常数，我们可以在递归时特殊维护两个端点的子树。

询问次数：不知道，反正能过。

时间复杂度 $\mathcal O(n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
extern "C" int ask(int x,int y,int z);
mt19937 rnd;
typedef vector<int> vi;
int n;
int chk(int rt,vi V) {
	int cnt=0,col=0;
	for(int i:V) {
		if(!cnt) ++cnt,col=i;
		else {
			if(ask(rt,i,col)==rt) --cnt;
			else ++cnt;
		}
	}
	if(!cnt) return rt;
	int tot=0;
	for(int i:V) if(ask(rt,col,i)!=rt) ++tot;
	return (tot<=n/2)?rt:-1;
}
int solve(int l,int r,vi L,vi R,vi C,vi S) {
	if((int)L.size()>n/2) return chk(l,L);
	if((int)R.size()>n/2) return chk(r,R);
	if(l==r) return chk(l,S);
	if(C.size()==2) {
		vi tmp=C; tmp.push_back(r);
		for(int i:R) tmp.push_back(i);
		int z=chk(l,tmp);
		if(~z) return z;
		tmp=C,tmp.push_back(l);
		for(int i:L) tmp.push_back(i);
		return chk(r,tmp);
	}
	int k=l;
	while(k==l||k==r) {
		int rd=rnd()%(C.size()+S.size());
		if(rd<(int)C.size()) k=C[rd];
		else {
			int t=S[rd-C.size()];
			for(int i:C) if(ask(k,t,i)==i) k=i;
		}
	}
	vector <int> CL,CR,SK,SL,SR;
	for(int i:C) if(i!=k) {
		if(ask(l,i,k)==i) CL.push_back(i);
		else CR.push_back(i);
	}
	for(int i:S) {
		if(ask(l,k,i)==k) {
			if(ask(r,k,i)==k) SK.push_back(i);
			else SR.push_back(i);
		} else SL.push_back(i);
	}
	int sl=L.size()+CL.size()+SL.size(),sr=R.size()+CR.size()+SR.size();
	if(sl<=n/2&&sr<=n/2) return chk(k,SK);
	if(sr>n/2) swap(L,R),swap(CL,CR),swap(SL,SR),swap(l,r);
	r=l;
	R.push_back(k);
	for(int i:SK) R.push_back(i);
	for(int i:CR) R.push_back(i);
	for(int i:SR) R.push_back(i);
	for(int i:CL) if(i!=l&&ask(i,r,l)==r) r=i;
	S.clear();
	for(int i:SL) {
		if(ask(l,r,i)==r) R.push_back(i);
		else S.push_back(i);
	}
	return solve(l,r,L,R,CL,S);
}
extern "C" int centroid(int id,int N,int M) {
	n=N;
	if(id==1) return ask(1,2,3);
	if(id==3||id==5) {
		int l=1,r=2;
		for(int i=3;i<=N;++i) {
			int u=ask(l,r,i);
			if(l==u) l=i;
			if(r==u) r=i;
		}
		vi arr(N);
		iota(arr.begin(),arr.end(),1);
		nth_element(arr.begin(),arr.begin()+N/2,arr.end(),[&](int x,int y) {
			return ask(x,y,r)==y;
		});
		return arr[N/2];
	}
	while(true) {
		int l=rnd()%n+1,r=rnd()%n+1;
		if(l==r) continue;
		vi L,R,C{l,r},S;
		for(int i=1;i<=n;++i) if(i!=l&&i!=r) {
			int z=ask(i,l,r);
			if(z==l) L.push_back(i);
			if(z==r) R.push_back(i);
			if(z==i) C.push_back(i);
			if(z==0) S.push_back(i);
		}
		int k=solve(l,r,L,R,C,S);
		if(~k) return k;
	}
	return 0;
}