P10220

· · 题解

提供一个和大众做法不一样的做法。

其实这个神秘做法是因为我想歪了，我如果一次走一步就和其他题解一样了，但我每次都直接走到一个叶子，然后性质很差。

和其他题解一样，我们先考虑 A 操作以后 B 第一个到达的点最大能是多少。

如果你唤醒了某个守卫，那这个守卫的右子树的点都被支配了，也就是会在这一轮无法被选中。

这个结构具有良好的性质，我们二分一个答案，然后用 dp 确定合法性。具体来说设 dp_{i,0/1} 表示已经考虑完以 i 为根的子树，且子树内还有/没有点没有被支配时需要花费的最小代价。

然后我们可以得到 B 第一个到达的点，设为 x，注意到这个树上的路径都是唯一的，我们不妨就让 B 直接走到 x。

接下来我们希望第二个，第三个，以及后面的被访问的点也可以通过类似上面的方法去求出来。

我们模拟 B 走路的过程，走到一个叶子以后会往上，然后再往下到一个没有任何一个点被访问的子树，访问完这个子树的所有点以后，又会往上，然后又往下走到一个更大的没被访问的子树。

如果我们当前走到了一个没有任何点被访问的子树的根的位置，我们希望像一开始一样，求出 A 当前可以让 B 到达的最大的位置。

这个问题看似是上一个问题的子问题，但是实际上直接做并不对。因为你现在已经钦定了 B 必须要先到这个第一个到达的点 x，而走到 x 是需要支付一定代价激活一些守卫的，但是这些激活的守卫可能还对后面的代价有影响，也就是说如果按照上面的做法继续做会存在后效性。

我们定义覆盖：如果 y 点的守卫被激活了，而且 x 在 y 的右子树内，则我们称 x 被 y 覆盖。

称一个最深的覆盖是对于一个 x 满足上述条件的深度最大的 y，容易注意到当守卫激活状态固定时 y 是唯一的。

考虑我们钦定第一个走到的位置是 x 实际上是怎样一个条件，也就是对于所有值 <x 的叶子，都存在一个点把它覆盖了。

可以推广的更一般的情况，如果当前访问到了没有任何一个点被访问的子树的根（定义看上面 B 的走路过程），设其为 u，钦定下一个被访问的点是 x'，那么能走到 x' 的条件是：

只考虑 u 子树内的守卫激活情况，对于所有值 <x' 的叶子，子树内存在一个点将其覆盖。

换句话说就是，对于所有 <x' 的位置，其最深覆盖点的深度大于等于 u 点的深度。

现在继续考虑这样一个问题：已经确定了 B 前 k 个走到的点是 s_1,s_2,...,s_{k}，现在需要判定下一个点走到 x 是否可行。

我们把限制全部列出来，相当于对于每个点有一个最深覆盖的深度限制。

这个东西就可以 dp 了，设 dp_{i,j} 表示以 i 为根的子树内，部分限制已经被满足，目前最严格的限制是 i 中某一点的最深覆盖深度要 \geq j。

转移每次枚举两边子树当前的限制，然后再枚举当前的点选不选。

可以用前缀优化做到 O(2^n n) 完成一次 dp。

然后确定了前若干次 B 访问到的点，我们继续按照上面 B 走路的过程模拟。如果我们确定了下一个 B 走过的叶子节点，我们就直接让 B 走到这个叶子节点然后继续上面的过程。

根本上这个过程是考虑到因为后面走到点的不确定，守卫的激活状态是不确定的，但是 B 前面走的路径却是确定的，所以其对覆盖关系的限制也能确定。直接钦定 B 下一个经过的叶子节点然后用 dp 去判断合法性。

这个暴力做法的复杂度就先不分析了，每尝试确定下一个点就要做一次 dp，所以复杂度大概是 O(4^n\operatorname{poly}n)。

我们知道满二叉树的结构非常优秀，我们尝试优化上述的过程。

我们考虑到一个没有任何点被访问的子树的根 u，然后尝试确定下一个位置的数，实际上只有 u 子树内的 dp 值和 u 祖先的 dp 值会发生变化，我们考虑每次做的时候只计算 u 子树内的变化，然后再向上合并。

这个东西乍一看，每次有一个二分，然后有 O(n) 次合并，每次合并是 O(n) 的，好像是 O(2^nn^3) 的。

考虑分析它。这个树上大小为 2^i 的子树只有 2_{n-i} 个，而在一个大小 2^i 的子树上二分需要 i 次，求和：

n^2\sum_i 2^{n-i}i = n^2\sum_i\sum_{j = 0}^i 2^{n-i} = n^2\sum_j\sum_{i = j}^n 2^{n-i} \leq n^2\sum_j 2^{n-j+1} \leq n^22^{n+2}

所以复杂度是 O(2^nn^2) 的。

#include<bits/stdc++.h>
using namespace std;
#define double long double
#define lowbit(x) (x&(-x))
#define int long long
const int inf = 1000000000000000;
int n,K;
vector<int>son[200005],val[200005];
int ll[200005],rr[200005],dep[200005];
int dp[200005][18];
int vis[200005];
int a[200005],p[200005],pos[200005];
int b[200005],c[200005];
int f[20],g[20];
vector<int>ans;
int tot;
//已经确定的限制 正在 check 的限制 
void build(int l,int r,int k){
    ll[k] = l,rr[k] = r;
    dep[k] = dep[k>>1]+1;
    if(l == r){son[k].push_back(k);val[k].push_back(p[k]);return;}
    int mid = l+r>>1;
    build(l,mid,k<<1),build(mid+1,r,k<<1|1);
    for(auto x:son[k<<1])son[k].push_back(x);
    for(auto x:son[k<<1|1])son[k].push_back(x);
    for(auto x:val[k<<1])val[k].push_back(x);
    for(auto x:val[k<<1|1])val[k].push_back(x);
}
void work(int now){
    if(now>=tot){
        for(int i =0;i<=n;i++)dp[now][i]=inf;
        dp[now][max(c[now],b[now])] = 0;
        return;
    }
    work(now<<1),work(now<<1|1);
    //钦定最大值在左边，什么都不用干
    int mn = inf,d = dep[now];
    for(int i = 0;i<d;i++){
        mn = min(mn,dp[now<<1|1][i]);
        dp[now][i] = dp[now<<1][i]+mn;
    } 
    mn = min(mn,dp[now<<1|1][d]);
    for(int i =0;i<d;i++){
        dp[now][i] = min(dp[now][i],min(dp[now<<1][i]+mn+a[now],inf));
    }
    mn = inf;
    //钦定最大值在右边
    for(int i =0;i<d;i++){
        mn = min(mn,dp[now<<1][i]);
        dp[now][i] = min(dp[now][i],dp[now<<1|1][i]+mn);
    } 
    //把右边的消掉 
}
void slove(int now,int tp){
    if(now==1)return;
    //从下向上合并 now 和他的兄弟
    int to = now^1;
    //需要讨论 now 在左边还是右边 
    int mn = inf,d = dep[now>>1];
//  cout << "!   " << to << endl;
//  for(int i =0;i<=d;i++)cout << dp[to][i] << " ";cout << endl;
    for(int i = 0;i<d;i++)g[i]=inf;
    for(int i = 0;i<d;i++){
        mn = min(mn,dp[to][i]);
        g[i] = f[i]+mn;
    }
    if(to&1){
        mn = min(mn,dp[to][d]);
        for(int i =0;i<d;i++){
            g[i] = min(g[i],min(f[i]+mn+a[now>>1],inf));
        }
    }
    mn = inf;
    for(int i =0;i<d;i++){
        mn = min(mn,f[i]);
        g[i] = min(g[i],dp[to][i]+mn);
    }
    if(now&1){
        mn = min(mn,f[d]);
        for(int i =0;i<d;i++){
            g[i] = min(g[i],min(dp[to][i]+mn+a[now>>1],inf));
        }
    }
    for(int i =0;i<d;i++)f[i] = g[i];
    if(tp){for(int i =0;i<d;i++)dp[now>>1][i] = f[i];}
    slove(now>>1,tp);
}
bool check(int now,int v){
    int d =dep[now];//cout << " " << d << endl;
    for(auto x:son[now])if(p[x]<v)c[x] = d;
    work(now);
    for(int i = 0;i<d;i++)f[i] = dp[now][i];
    for(int i = d;i<=n;i++)f[i] = inf;
    slove(now,0);
    for(auto x:son[now])c[x] = 0;
    return (f[0]<=K);
}
void dfs(int now,int to = 0){
    int l = ll[now],r = rr[now],d = dep[now];
    //cout << now << " " << to << " " << l << " " << r << endl;
    // to 是某个叶子在序列中的位置，如果没有就找一个
    if(now>=tot){ans.push_back(p[now]);return;}
    if(!to){
        //否则在子树里面二分
        int l = 0,r = val[now].size()-1;
        while(l<r){
            int mid = l+r+1>>1;
            if(check(now,val[now][mid])){
                l = mid;
            }else r = mid-1;
        }
        to = pos[val[now][l]]+tot-1;
        for(auto x:son[now])if(p[x]<val[now][l])b[x] = d;
        work(now);
    //  cout << " >  " << now << endl;
    //  for(int i =0;i<d;i++)cout << dp[now][i] <<" ";cout << endl;
        for(int i =0;i<d;i++)f[i] = dp[now][i];
        slove(now,1);
    //  cout << " " << now << " " << pos[val[now][l]] << endl;
    }
    int ppos = to-tot+1;
    int mid = l+r>>1;
    if(ppos<=mid){
        dfs(now<<1,to);
        dfs(now<<1|1,0);
    }else{
        dfs(now<<1|1,to);
        dfs(now<<1,0);
    }
}
void solve(){

    cin >> n >> K;
    tot = 1<<n;
    for(int i =0;i<=tot*2;i++)son[i].clear(),val[i].clear();
    ans.clear();
    for(int i =0;i<=tot*2;i++)for(int j =0;j<=n;j++)dp[i][j] = 0;
    for(int i =0;i<=tot*2;i++)vis[i] = b[i] = c[i]=0;

    for(int i = 1;i<=(1<<n)-1;i++)cin >> a[i];
    for(int i = (1<<n);i<=(1<<n+1)-1;i++)cin >> p[i];
    for(int i = (1<<n);i<=(1<<n+1)-1;i++)pos[p[i]] = i-tot+1;
    build(1,tot,1);
    for(int i =0;i<=tot*2;i++)sort(val[i].begin(),val[i].end());
    dfs(1,0);
    for(auto x:ans)cout << x << " ";cout << '\n';
}
signed main(){
    //freopen("maze5.in","r",stdin);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin >> t;
    while(t--)solve();
    return 0;
}/*
1
3 3
3 2 1 2 1 2 1
4 2 6 3 7 1 5 8
*/