题解：P11091 [ROI 2021] 工作报告 (Day 1)

· · 题解

题目传送门。

下文默认 \sum m_i 和 n 同阶。

容易证明当一个子树内最小值固定时，最大值越小越好。所以不妨设 g_{x,i} 表示 x 子树内最小值为 i 时最大值的最小值（可以看成维护区间）。对每个点枚举全排列更新答案可以做到 O(n^2k!)。

考虑优化，显然每个点的答案可以用状压来计算。设 f_{x,i,S} 表示考虑了 S 内的子树的答案。此时转移是容易的，可以做到 O(n^22^kk)。

此时状态已经不好优化，这个东西也没法用数据结构维护，所以考虑观察性质。一个显然的事情就是若存在 l_1\le l_2\le r_2\le l_1，那么 [l_1,r_1] 这个状态就是无用的。我们可以考虑对于每个点只保留有用的状态，记 x 子树内的状态为 S_x。则复杂度为 O(\sum |S_i|(2^kk+\log n))，\log n 是因为要排序。

另一个优化是若 x 的儿子只有一个，那么就不需要管它。

接下来我们要证明 \sum |S_i| 是 O(n\log n) 的。

对于一个点 x，设 x 的儿子为 c_1,\cdots,c_k(k\ge2)。记它 |S| 最大的点为 v。显然 S_x 中的每一个区间的 2 端来自不同的子树，又因为每个区间最多出现在端点处 2 次（分别作为起点和终点），所以有 |S_x|\le 2(\sum |S_{c_i}|-|S_v|)。

显然 |S_x| \le \sum |S_{c_i}|。

考虑类似启发式合并的证明。若 2|S_v|\le\sum |S_{c_i}|，则每个区间在贡献一次后大小都至少乘 2，最多贡献 \log n 次。否则可以看成是除了最大值以外的点都至少乘 2，而最大值只往上走了 \sum |S_{c_i}|-|S_v|，这一部分大小也乘了 2，所以每个点还是最多贡献 \log n 次。

所以总的时间复杂度为 O(n\log n(2^kk+\log n))，不满。实现的时候要特别注意只有一个儿子的情况。

输出方案是简单的。

code

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define uint unsigned int
#define pii pair<int,int>
#define io ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
inline int read(){
    int x=0;bool f=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return f?x:-x;
}
int n,dp[256],lst[256],vs[256],top,now,cnt,l[100005],r[100005],ans[100005];
pii v[100005],stk[100005],zpd[50000000];
vector<int> g[100005],ord[100005];
void dfs(int x){
    if(!g[x].size()) return ;
    for(int y:g[x])
        dfs(y);
    if(g[x].size()==1) return l[x]=l[g[x][0]],r[x]=r[g[x][0]],void();
    for(int y:g[x])
        for(int i=l[y];i<=r[y];i++)
            ans[zpd[i].first]=114514;
    int cntv=0;top=0;
    for(int i=0;i<g[x].size();i++)
        for(int j=l[g[x][i]];j<=r[g[x][i]];j++){
            auto z=zpd[j];
            memset(dp,63,sizeof(dp));
            dp[1<<i]=z.second;
            for(int s=0;s<(1<<g[x].size());s++)
                if(s&(1<<i))
                    for(int j=0;j<g[x].size();j++)
                        if(j!=i&&(s&(1<<j))){
                            int pos=lower_bound(zpd+l[g[x][j]],zpd+r[g[x][j]]+1,(pii){dp[s^(1<<j)],0})-zpd;
                            if(pos!=r[g[x][j]]+1)
                                dp[s]=min(dp[s],zpd[pos].second);
                        }
            if(dp[(1<<g[x].size())-1]<ans[z.first])
                ans[z.first]=dp[(1<<g[x].size())-1];
        }
    for(int y:g[x])
        for(int i=l[y];i<=r[y];i++){
            auto z=zpd[i];
            if(ans[z.first]<114514)
                v[++cntv]={z.first,ans[z.first]},ans[z.first]=114514;
        }
    sort(v+1,v+cntv+1);
    for(int i=1;i<=cntv;i++){
        pii y=v[i];
        while(top&&stk[top].second>=y.second) top--;
        stk[++top]=y;
    }
    l[x]=now+1;
    for(int i=1;i<=top;i++) zpd[++now]=stk[i];
    r[x]=now;
} 
void solve(int x,int p){
    if(!g[x].size()) return ord[x].push_back(zpd[p].first);
    if(g[x].size()==1) return ord[x].push_back(g[x][0]),solve(g[x][0],p);
    for(int y:g[x])
        for(int i=l[y];i<=r[y];i++)
            ans[zpd[i].first]=114514;
    int cntv=0;top=0;
    for(int i=0;i<g[x].size();i++)
        for(int j=l[g[x][i]];j<=r[g[x][i]];j++){
            auto z=zpd[j];
            if(z.first!=zpd[p].first) continue;
            memset(dp,63,sizeof(dp));
            dp[1<<i]=z.second,lst[1<<i]=i,vs[1<<i]=j;
            for(int s=0;s<(1<<g[x].size());s++)
                if(s&(1<<i))
                    for(int j=0;j<g[x].size();j++)
                        if(j!=i&&(s&(1<<j))){
                            int pos=lower_bound(zpd+l[g[x][j]],zpd+r[g[x][j]]+1,(pii){dp[s^(1<<j)],0})-zpd;
                            if(pos!=r[g[x][j]]+1&&zpd[pos].second<dp[s])
                                dp[s]=zpd[pos].second,lst[s]=j,vs[s]=pos;
                        }
            if(dp[(1<<g[x].size())-1]==zpd[p].second){
                int s=(1<<g[x].size())-1;
                vector<int> vv;vv.clear();
                while(s) ord[x].push_back(g[x][lst[s]]),vv.push_back(vs[s]),s^=(1<<lst[s]);
                for(int i=0;i<vv.size();i++)
                    solve(ord[x][i],vv[i]);
                reverse(ord[x].begin(),ord[x].end());
                return ;
            }
        }
}
int main(){
    n=read();
    for(int i=1,x;i<=n;i++){
        x=read();
        if(x==1){
            x=read();
            for(int j;x--;)
                j=read(),g[i].push_back(j);
        }
        else{
            x=read();
            l[i]=now+1;
            for(int j;x--;)
                j=read(),zpd[++now]={j,j};
            r[i]=now;sort(zpd+l[i],zpd+r[i]+1);
        }
    }
    dfs(1);
    if(r[1]>=l[1]){
        cout<<"Yes\n";
        solve(1,l[1]);
        for(int i=1;i<=n;i++,cout<<'\n')
            for(int x:ord[i])
                cout<<x<<' ';
    }
    else cout<<"No\n";
    return 0;
}