自动搬运

查看原文

来自洛谷，原作者为

	Wei_Han 盛夏书写狂野的诗篇，明月下的少年和连绵的蝉鸣

搬运于2025-08-24 23:09:22，当前版本为作者最后更新于2025-08-15 15:20:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑一个暴力 dp，设 $f_{u,j}$ 表示以 $u$ 为根的子树，$u$ 的数交换过后是 $j$ 的最小代价，转移是 $O(nV^2)$ 的。

发现上面的状态其实是冗余的，对于要求的数 $m$，其实只把所有数分为了三类 $<m$,$=m$,$>m$，因此，考虑以此重新设计状态优化，即 $f_{u,0/1/2}$ 表示以 $u$ 为根的子树，$u$ 节点上的数 $<m$，$=m$，$>m$ 枚举转移即可，单次查询复杂度 $O(n)$，总复杂度 $O(nq)$。

进一步地考虑优化，发现所有数最多只会有两次状态变换，换句话讲，假如每有一个点初值修改我们就跑一遍 dp，修改操作只会有 $O(n)$ 个，而本题给定了是完全二叉树，因此树高只有 $O(\log n)$，考虑暴力修改，每次更新一个点初值，然后再更新其父亲，逐个向上，单次修改复杂度 $O(\log n)$，总复杂度 $O(q+n\log n)$。

具体实现可以将询问离线，排序后指针扫描逐个加点。

const ll N=1e6+5,M=2e4+5;
ll n,q,fa[N],f[N][3],b[N],c[N],ans[N],g[N][3],vis[N];
struct node{ll i,a,c;}a[N];
vector<pii> A;vector<ll> G[N];
inline ll med(ll x,ll y,ll z){ll mx=max({x,y,z});if(x==mx) return max(y,z);if(y==mx) return max(x,z);return max(x,y);}
inline void dfs(ll x,ll fa)
{
    f[x][2]=0,f[x][0]=f[x][1]=c[x];ll ls=0,rs=0;vis[x]=2;
    for(ll y:G[x]) if(y!=fa) dfs(y,x),ls?rs=y:ls=y;
    if(!ls||!rs) return;g[x][0]=g[x][1]=g[x][2]=inf;
    fo(0,i,2) fo(0,j,2) fo(0,k,2) ckmn(g[x][med(i,j,k)],f[ls][i]+f[x][j]+f[rs][k]);
    fo(0,i,2) f[x][i]=g[x][i];
}
inline void upd(ll x,ll k)
{
    if(!x) return;
    if(vis[x]==0) f[x][0]=0,f[x][1]=f[x][2]=c[x];
    if(vis[x]==1) f[x][1]=0,f[x][0]=f[x][2]=c[x];
    if(vis[x]==2) f[x][2]=0,f[x][0]=f[x][1]=c[x];
    ll ls=0,rs=0;for(ll y:G[x]) if(y!=fa[x]) ls?rs=y:ls=y;
    if(!ls||!rs) return upd(fa[x],2);g[x][0]=g[x][1]=g[x][2]=inf;
    fo(0,i,2) fo(0,j,2) fo(0,k,2) ckmn(g[x][med(i,j,k)],f[ls][i]+f[x][j]+f[rs][k]);
    fo(0,i,2) f[x][i]=g[x][i];
    upd(fa[x],2);
}
signed main(){
    // freopen("median.in","r",stdin);
    // freopen("median.out","w",stdout);
    read(n,q);fo(1,i,n) (i!=1?G[i/2].pb(i),G[i].pb(i/2):void()),fa[i]=i/2,read(a[i].a,a[i].c),c[i]=a[i].c,b[i]=a[i].c,a[i].i=i;
    sort(a+1,a+1+n,[&](node i,node j){return i.a<j.a;});ll x,y;
    fo(1,i,q) read(x),A.pb(mk(x,i));sort(all(A));
    ll i1=1,i2=1;dfs(1,0);
    for(auto [x,id]:A)
    {
        while(i2<=n&&a[i2].a<x) ++i2;
        while(i1<=n&&a[i1].a<x) vis[a[i1].i]=0,upd(a[i1].i,0),++i1;
        while(i2<=n&&a[i2].a==x) vis[a[i1].i]=1,upd(a[i2].i,1),++i2;
        // wr(x),pp,wr(id),pp,wr(i1),pp,wr(i2),pr;
        ans[id]=f[1][1];
    }
    fo(1,i,q) wr(ans[i]),pr;
    return 0;
}