自动搬运

查看原文

来自洛谷，原作者为

	P_Bisector 天天爱打卡？

搬运于2025-08-24 23:07:12，当前版本为作者最后更新于2025-08-03 13:27:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题解疑似乱搞，欢迎来 hack 或证明。

正文

首先证明最多两次能量传递就能激活所有宝石。考虑数学归纳法。下文中称树的高度为所有点的深度的最大值，根节点的深度为 $0$。

• 只有一个点的时候，显然无需能量传递，小于两步。

• 考虑在原先点集中增加一个点。首先，前面所有点一定可以构成一棵高度小于等于 $2$ 的最短路树。设其根为 $rt$。对于这个新增点$i$，如果存在一条边 $rt\rightarrow i$，那么将 $i$ 挂在 $rt$ 下方即可。否则遍历所有深度为 $1$ 的点 $j$。如果存在一条边 $j\rightarrow i$ 那么将 $i$ 挂在 $j$ 下方即可。如果均不满足，则将 $rt$ 和所有 $j$ 挂在 $i$ 下方即可。

以上这一段不仅证明了最短路树高度不超过 $2$ 并且给出了构造方案。按照这个构造方案建树即可通过本题（证明暂无，可能是数据太弱）。不知道凭啥能过，不放心可以加一个 random_shuffle。（不加 random_shuffle也能过。）

::::info[代码如下]

#include<bits/stdc++.h>
#define B __int128
#define PLL pair<int,int>
using namespace std;
const int inf=1e18,N_=100050,mod=998244353,P=1e9+7,N=1e6+50,N2=5050;
bool sense(int i, int j);
int fa[N],rt,a[N];
void insert(int x,int n){
	int S=sense(rt,x);
	if(S){fa[x]=rt;return;}
	vector<int>v;
	for(int i=1;i<n;i++){
		if(fa[a[i]]==rt){
			v.push_back(a[i]);
		}
	}
	for(int i=0;i<v.size();i++){
		int R=v[i];
		int SR=sense(R,x);
		if(SR){fa[x]=R;return;}
	}
	fa[rt]=x,rt=x; 
	for(int i=0;i<v.size();i++){
		fa[v[i]]=x;
	}
}
int altar(int n){
	for(int i=1;i<=n;i++)g[i].clear(),fa[i]=0,a[i]=i;
	random_shuffle(a+1,a+1+n);
	rt=a[1];
	for(int i=2;i<=n;i++){
		insert(a[i],i);
	}
	return rt;
}

::::