题解：P17240 [IOI 2026] 弹球机 / ballmachine

· · 题解

vp 的时候猛攻 T2 去了，最后剩下不到 1.5h 做 T1 结果 M 次做歪了做出了一个没啥道理的 M+1 次。vp 结束后认真做了一段时间大彻大悟了。

我 vp 时的 M+1 次，虽然没啥用但是讲一下引入问题：

考虑先按照 0 \sim M-1 的顺序给第 i 个叶子塞编号为 i 的球直到塞满，然后收集一次即可获取叶子的一个 dfs 序，然后我们倒过来塞一遍叶子即可获得 dfs 序相邻的叶子的 LCA 深度，随后便可还原树。

考虑 M 次的做法：

我们考虑一个形式比较简单的操作，按照 0 \sim M-1 的顺序给第 i 个叶子塞编号为 M-i-1 的球直到塞满，然后收集一次获得序列 seq。我们从前往后扫描 seq，如果下一个位置颜色不同且编号小于自己那么一定是当前点的一个儿子，我们可以根据其是否是对应颜色的最后一次出现算出其是叶子还是非叶子结点，然后我们递归这个儿子。而如果下一个位置与自己不同且编号大于自己那么一定是回溯了，我们就回溯看看回到了哪个位置。

否则如果下一个位置和自己颜色相同，那么一定有下一个位置是自己的某个儿子，我们依然递归这个儿子即可。

这个做法通过先走不同颜色的儿子避免了我们算不出不同的颜色链之间的 LCA 深度的问题。

接下来我们开始尝试解决原问题，注意到 C 比较大，猜测可能是 \sqrt M 有关的算法，考虑对叶子分成 \sqrt M 块，我们不断加入新的块，将新的块内的叶子按照前面的 M 次的办法去处理，所以问题是对于结构已经清晰的树 T，我们需要找到一个只用 \sqrt M 种标号的办法区分其哪些点会挂上新的链。

我们考虑一个极端情况，假如树 T 是一个菊花，那么我们无论如何都区分不出所有叶子，这说明什么？这说明由于叶子不会挂新链，我们没必要区分所有叶子。

考虑设计一个递归的编号函数 solve(u)，我们先对 u 的儿子 v_1 \sim v_k 执行 solve(v_i)，然后对于所有叶子 v_i，我们将其标号为特殊标号，对于剩下的儿子 v'_1 \sim v'_{k'}，我们考虑使用儿子的标号和进入儿子子树后第一个标号也就是最小标号来区分所有儿子。

这个想法非常有道理，因为两个数 \sqrt M \times \sqrt M 的组合可以区分出 M 个不同的儿子，更具体地我们发现需要对 v'_i 的儿子标号二次标号，设其儿子有 d_{v'_i} 个不同标号，我们考虑如下构造：

将所有 v'_i 看作长度为 d_{v'_i} 的线段，将其首尾相连排布在数轴上，对于 v'_i 我们将其本身的标号设置为线段右端点除以 \sqrt M 下取整的结果，将其儿子重标号为其对应的线段覆盖住的点 \bmod \sqrt M 的结果，假设儿子的不同标号数量不超过 \sqrt M，这个构造方法就不会导致编号冲突。并且由于 \sum d_{v'_i} \leq M，所以当前点的儿子编号不会超过 \frac{M}{\sqrt M} 也就是 \sqrt M，所以前面的假设可以成立。

现在我们已经可以区分出 T 上所有可以挂新链的位置链，加入新链就考虑将新块的标号平移到树 T 的区分标号之后，加入顺序就是先将 T 上每个点的颜色放对，再从小往大在新块的叶子处塞球直到塞满，那么 dfs 时我们会优先进入新链部分，在新链部分可以按照前面 M 次的办法处理，在考虑树 T 的部分时，我们找出下一个树 T 中的点，根据这个点和当前点区分出会走到哪个儿子（或者走到了一个不区分的叶子），如果不能走到新链部分并且儿子走完了就回溯。

这个做法需要大概 2 \sqrt M 个标号和 \sqrt M 轮，已经可以通过了，进行一些调参可以卡到 \max C = 41。

#include<bits/stdc++.h>

bool insert(int U, int X);
std::vector<int> collect();

std::vector<int> find_structure(int M);
using namespace std;
const int maxn = 1114;
int nd;
int rt;//rt 初始为极大值
vector<int> E[maxn];
int col[maxn];
const int warma = 14;//每 warma 个叶子做一次
int spec;
bool cmp(int x,int y){
    return E[x].size()>E[y].size();
}
int leaf[maxn];
vector<int> vec;
void dfs(int u){
    vec.push_back(u);
    if(E[u].size()==0){
        leaf[u]=u;
        return ;
    }
    vector<int> son;
    for(int v:E[u]){
        dfs(v);
        leaf[u]=leaf[v];
        if(E[v].size()==0) col[v]=-1;
        else{
            son.push_back(v);
        }
    }
    sort(son.begin(),son.end(),cmp);
    int id=0;
    int index=0;
    for(int i=0;i<(int)son.size();i++){
        int v=son[i];
        map<int,int> f;
        for(int w:E[v]){
            if(f.find(col[w])==f.end()) f[col[w]]=id++;
            if(id>=12){
                id-=12;
                if(i!=0) index++;
            }
        }
        for(int w:E[v]) col[w]=f[col[w]];
        col[v]=index;
    }
    return ;
}
set<int> S;
int Last[maxn];
void build(int u,vector<int> &dfn,int &pos,int R){
    S.insert(u);
    int now=dfn[pos];
    while(pos+1<(int)dfn.size()){
        if(dfn[pos+1]>now) return ;
        int v=-1;
        if(pos+1==Last[dfn[pos+1]]) v=R-dfn[pos+1]-1;
        else v=nd++;
        E[u].push_back(v);
        pos++;
        build(v,dfn,pos,R);       
    }
}
void solve(int u,vector<int> dfn,int &pos,int R,int lim){
    S.insert(u);
    int now=dfn[pos];
    if(dfn[pos]<lim){
        //新增的节点
        while(pos+1<(int)dfn.size()){
            if(dfn[pos+1]>now) return ;
            int v=-1;
            if(pos+1==Last[dfn[pos+1]]) v=R-dfn[pos+1]-1;
            else v=nd++;
            E[u].push_back(v);
            pos++;
            solve(v,dfn,pos,R,lim);
        }   
    }else{
        //原有的节点
        int d=E[u].size();
        vector<int> son;
        while(d>0){
            if(dfn[pos+1]<lim){
                int v=-1;
                if(Last[dfn[pos+1]]==pos+1) v=R-dfn[pos+1]-1;
                else v=nd++;
                son.push_back(v);
                pos++;
                solve(v,dfn,pos,R,lim);
            }else{
                d--;
                //判别进入了哪个儿子
                int Leaf=-1;
                for(int v:E[u]){
                    if(E[v].size()==0) Leaf=col[v];
                }
                if(dfn[pos+1]==Leaf){
                    pos++;
                    //进入了哪个叶子都不重要
                }else{
                    for(int v:E[u]){
                        if(E[v].size()>0){
                            int mi=1e9;
                            for(int w:E[v]) mi=min(mi,col[w]);
                            //找到 pos+1 后面第一个 >=lim 的
                            int l=pos+2;
                            while(dfn[l]<lim) l++;
                            if(dfn[pos+1]==col[v]&&dfn[l]==mi){
                                pos++;
                                solve(v,dfn,pos,R,lim);
                                break;
                            }
                        }
                    }
                }
            }
        }
        for(int v:son) E[u].push_back(v);
    }
}
std::vector<int> find_structure(int M){
    nd=M;    
    int rt=1000;
    //[0,warma)
    int L=0,R=min(warma,M);
    for(int i=L;i<R;i++){
        while(insert(i,R-i-1)==true);
    }
    vector<int> dfn=collect();
    memset(Last,0,sizeof(Last));
    for(int j=0;j<(int)dfn.size();j++) Last[dfn[j]]=j;
    int pos=0;
    build(rt,dfn,pos,R);
    for(int i=warma;i<M;i+=warma){
        int L=i,R=min(M,i+warma);
        vec.clear();
        col[rt]=0;
        dfs(rt);
        int mx=0;
        for(int x:S){
            if(col[x]!=-1) mx=max(mx,col[x]);
        }
        mx++;
        for(int x:S){
            if(col[x]==-1) col[x]=mx;
        }
        mx++;
        //[0,R-L)
        for(int x:S){
            col[x]+=R-L;
        }
        //放置
        for(int x:vec){
            insert(leaf[x],col[x]);
        }
        for(int i=L;i<R;i++){
            while(insert(i,R-i-1)==true);
        }
        dfn=collect();
        memset(Last,0,sizeof(Last));
        for(int j=0;j<(int)dfn.size();j++) Last[dfn[j]]=j;
        pos=0;
        solve(rt,dfn,pos,R,R-L);//这个过程中更新 S
    }
    int n=nd+1;
    vector<int> fa(n-1);
    for(int i=0;i<nd;i++){
        for(int j:E[i]) fa[j]=i;
    }
    for(int j:E[rt]) fa[j]=n-1;
    return fa;
}