「题解」P9558 [SDCPC2023] Trie

do_while_true · 2023-09-10 08:41:39 · 题解

orz negiizhao

自底向上确定每个点的所有出边上挂的字符，那么问题就是比较 x,y 两个子树的字典序大小。直接一起往下 dfs，先找到标记点的子树更小，如果 dfs 过程中一棵树找完了而另一棵树没找完并且还没确定大小，这时还没找完的那棵树应当排到前面。在递归的最浅层也就是比较 x,y 时最后特判下标号大小即可。

这里排序使用归并排序 stable_sort，现在来分析一下复杂度：

单独考虑每一层：在归并两个队头分别为 u,v 的子树序列 p,q 时，花费 \min(size_u,size_v) 的时间代价，将其中之一 pop 掉。先把代价放缩成 pop 掉的那个子树的 size，但如果 pop 掉的是重儿子是把代价记成没有被 pop 掉的那个轻儿子上。这样每个轻儿子计算代价时最多被计算两次，所以同一层所花费的是轻儿子子树和级别的。再算上归并排序一共有 \log 层，那么时间复杂度就是 \mathcal{O}(n\log^2 n)．

const int N=200010;
int n,m;
int fa[N],vis[N],col[N],siz[N];
vi eg[N];
void dfs1(int x){
    siz[x]=1;
    for(auto v:eg[x])dfs1(v),siz[x]+=siz[v];
    stable_sort(eg[x].begin(),eg[x].end(),[&](const int &x,const int &y){
        function<int(int,int)>cmp=[&](int u,int v){//u<v:1  v<u:-1  u=v:0
            if(vis[u]+vis[v]==1)return vis[u]?1:-1;
            int len=min(eg[u].size(),eg[v].size());
            for(int i=0;i<len;i++){
                int t=cmp(eg[u][i],eg[v][i]);
                if(t)return t;
            }
            if(siz[u]==siz[v]){
                if(u==x&&v==y)return u<v?1:-1;
                return 0;
            }
            else return siz[u]>siz[v]?1:-1;
        };
        return cmp(x,y)==1?1:0;
    });
    int len=eg[x].size();
    for(int i=0;i<len;i++)col[eg[x][i]]=i;
}
void solve(){
    read(n,m);
    for(int i=0;i<=n;i++)vi().swap(eg[i]),vis[i]=0;
    for(int i=1;i<=n;i++)read(fa[i]),eg[fa[i]].pb(i);
    for(int i=1,x;i<=m;i++)vis[read(x)]=1;
    dfs1(0);
    for(int i=1;i<=n;i++)putchar('a'+col[i]);
    puts("");
}