题解：P11423 [清华集训 2024] 阿尔塔尔 2

P_Bisector · 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;
}

::::