题解归档 - cf2220F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2220F
• 本地来源：problems/cf2220F/idea.md
• 题目链接：https://codeforces.com/contest/2220/problem/F
• 原始标题：cf2220F — MEX Replacement on Tree

思路

cf2220F — MEX Replacement on Tree

题意

根为 1 的树，点权为 0..n-1 的排列。对点 v，设根到 v 路径上权值集合为 S_v，定义 f(v)=MEX(S_v)。最多一次操作：选点 v，令 p_v ← f(v)。求 Σ f(v) 的最大值。

做法

基础答案

DFS 维护值域 [0,n] 线段树：位置 x 为 1 表示当前路径缺值 x，进点标记 p_v 为 0，查询最左 1 即 mex1(v)；再查 mex1+1 得 mex2(v)。欧拉序 [tin,tout] 表示子树。

基础分 base = Σ mex1(v)。

操作增益

对操作点 v：令 a=p_v，m=mex1(v)，仅当 a>m 可能正增益。

• 负贡献（Case A，mex1(u)>a）：a - mex1(u)。按 mex1 从 n 扫到 0，欧拉序线段树维护已插入点的 mex1 之和与个数；对 p_v=i 查子树得 neg(v)=i·C-Σ。
• 正贡献（Case B，mex1(u)=m）：min(a,mex2(u))-m。按 mex1 分组，组内欧拉树初始值 mex2-m；按操作点权 a 降序，将 mex2>a 的点改为 -m 并记 count；pos(v)=sum+count·a。

gain(v)=pos(v)+neg(v)，答案 base + max(0, max gain)。

复杂度 O(n log n) / 测。

尝试记录

• 持久化 DFS + 链式扩展：小样例接近但子树混合 mex 时仍有 +1 误差。
• 欧拉序 pos/neg 初版：V.qry 左子树搜索 bug；负贡献 sweep 漏 mex1=n；正贡献组 cleanup 在 transition 后多减 (m2-m) 导致多测污染。

结论

AC 思路见 CF Step 官方题解（pos/neg 分解）；实现关键为 mex1 扫 n..0 与每组处理完 clr 欧拉线段树。

代码

来源：problems/cf2220F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:07:01
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
const ll inf=1e18;
vector<ll>ss[maxn],grp[maxn],atp[maxn];
ll p[maxn],m1[maxn],m2[maxn],tin[maxn],tout[maxn],cur,nn;
ll neg[maxn],pos[maxn],ab[maxn];
struct tnode{
    ll l,r,mn;
};
struct valseg{
    tnode t[4*maxn+5];
    void pu(ll rt){
        t[rt].mn=min(t[rt*2].mn,t[rt*2+1].mn);
    }
    void bd(ll rt,ll l,ll r){
        t[rt].l=l,t[rt].r=r;
        if(l==r){
            t[rt].mn=1;
            return;
        }
        ll mid=(l+r)/2;
        bd(rt*2,l,mid),bd(rt*2+1,mid+1,r);
        pu(rt);
    }
    void chg(ll rt,ll x,ll v){
        if(t[rt].l==t[rt].r){
            t[rt].mn=v;
            return;
        }
        ll mid=(t[rt].l+t[rt].r)/2;
        if(x<=mid) chg(rt*2,x,v);
        else chg(rt*2+1,x,v);
        pu(rt);
    }
    ll qry(ll rt,ll st){
        if(st>t[rt].r) return inf;
        if(t[rt].mn==1) return max(st,t[rt].l);
        if(t[rt].l==t[rt].r) return inf;
        ll mid=(t[rt].l+t[rt].r)/2,res;
        if(st<=mid){
            res=qry(rt*2,st);
            if(res!=inf) return res;
        }
        if(st<=mid+1) return qry(rt*2+1,mid+1);
        return qry(rt*2+1,st);
    }
}V;
struct eseg{
    ll s[4*maxn+5];
    void clr(ll rt,ll l,ll r){
        s[rt]=0;
        if(l==r) return;
        ll mid=(l+r)/2;
        clr(rt*2,l,mid),clr(rt*2+1,mid+1,r);
    }
    void add(ll rt,ll l,ll r,ll x,ll v){
        if(l==r){
            s[rt]+=v;
            return;
        }
        ll mid=(l+r)/2;
        if(x<=mid) add(rt*2,l,mid,x,v);
        else add(rt*2+1,mid+1,r,x,v);
        s[rt]=s[rt*2]+s[rt*2+1];
    }
    ll sum(ll rt,ll l,ll r,ll ql,ll qr){
        if(ql>qr) return 0;
        if(ql<=l and r<=qr) return s[rt];
        ll mid=(l+r)/2,res=0;
        if(ql<=mid) res+=sum(rt*2,l,mid,ql,qr);
        if(qr>mid) res+=sum(rt*2+1,mid+1,r,ql,qr);
        return res;
    }
}S,C;
struct zc{
    ll id,pd;
};
vector<zc>ord;
void dfs(ll u,ll fa){
    ll i,v;
    tin[u]=++cur;
    V.chg(1,p[u],0);
    m1[u]=V.qry(1,0);
    m2[u]=V.qry(1,m1[u]+1);
    if(m2[u]>nn) m2[u]=nn;
    grp[m1[u]].push_back(u);
    atp[p[u]].push_back(u);
    for(i=0;i<(ll)ss[u].size();i++){
        v=ss[u][i];
        if(v==fa) continue;
        dfs(v,u);
    }
    V.chg(1,p[u],1);
    tout[u]=cur;
}
int main(){
    ll t,n,i,j,k,u,v,base,ans,best,gain,a,m,cnt,sg;
    cin>>t;
    while(t--){
        cin>>n;
        nn=n;
        for(i=0;i<=n;i++){
            grp[i].clear();
            atp[i].clear();
        }
        for(i=1;i<=n;i++){
            ss[i].clear();
            ab[i]=0;
            cin>>p[i];
        }
        for(i=1;i<n;i++){
            cin>>u>>v;
            ss[u].push_back(v);
            ss[v].push_back(u);
        }
        cur=0;
        V.bd(1,0,n);
        dfs(1,0);
        base=0;
        for(i=1;i<=n;i++) base+=m1[i];
        for(i=1;i<=n;i++) neg[i]=pos[i]=0;
        S.clr(1,1,n);
        C.clr(1,1,n);
        for(i=n;i>=0;i--){
            for(j=0;j<(ll)grp[i].size();j++){
                u=grp[i][j];
                S.add(1,1,n,tin[u],m1[u]);
                C.add(1,1,n,tin[u],1);
            }
            for(j=0;j<(ll)atp[i].size();j++){
                u=atp[i][j];
                cnt=C.sum(1,1,n,tin[u],tout[u]);
                sg=S.sum(1,1,n,tin[u],tout[u]);
                neg[u]=i*cnt-sg;
            }
        }
        S.clr(1,1,n);
        C.clr(1,1,n);
        for(i=0;i<=n;i++){
            if(grp[i].empty()) continue;
            m=i;
            for(j=0;j<(ll)grp[m].size();j++){
                u=grp[m][j];
                S.add(1,1,n,tin[u],m2[u]-m);
            }
            ord.clear();
            for(j=0;j<(ll)grp[m].size();j++){
                u=grp[m][j];
                if(p[u]>m){
                    zc z;
                    z.id=u;
                    z.pd=p[u];
                    ord.push_back(z);
                }
            }
            sort(ord.begin(),ord.end(),[](zc x,zc y){
                return x.pd>y.pd;
            });
            for(j=0;j<(ll)ord.size();j++){
                a=ord[j].pd;
                u=ord[j].id;
                for(k=0;k<(ll)grp[m].size();k++){
                    v=grp[m][k];
                    if(ab[v]) continue;
                    if(m2[v]>a){
                        ab[v]=1;
                        S.add(1,1,n,tin[v],-m2[v]);
                        C.add(1,1,n,tin[v],1);
                    }
                }
                pos[u]=S.sum(1,1,n,tin[u],tout[u])+C.sum(1,1,n,tin[u],tout[u])*a;
            }
            S.clr(1,1,n);
            C.clr(1,1,n);
            for(j=0;j<(ll)grp[m].size();j++) ab[grp[m][j]]=0;
        }
        best=0;
        for(i=1;i<=n;i++){
            if(p[i]<=m1[i]) continue;
            gain=pos[i]+neg[i];
            best=max(best,gain);
        }
        ans=base+best;
        cout<<ans<<"\n";
    }
    return 0;
}