根号

Legitimity · 2023-04-24 13:15:17 · 题解

可以根号。

考虑简单暴力，确定一种颜色在最终集合后怎么做。维护当前颜色 i 的的极小联通子树 T_i，设其根为 rt。向其中加点 x 时将路径 (x,rt) 上的未加入的颜色的所有点加入。过程是可以看成在线的，即可以在 O(k) 的时间内求出加入 T 的前 k 个点构成的极小联通子树。

直接对每个颜色做是不太行的，考虑根号分治。对于一种颜色，只处理其 T 的前 B 个点，如果能构成就计入答案。之后剩下没有被计算的 T_i 都满足 |T_i|>B，每次随机点并跑一次该过程，期望 O(\dfrac{n}{B}) 次能找到一个在最终集合的点。

复杂度是 O(n\sqrt{n})，实际阈值可以取的离谱些，反正数据很难卡掉。

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n,k,col[200005],used[200005],ord[200005];
int fa[200005],dep[200005],vis[200005],inq[200005],tot;
vec e[200005],vt[200005],q;
void dfs(int x,int Fa){
    fa[x]=Fa,dep[x]=dep[Fa]+1;
    for(int y:e[x]) if(y^Fa) dfs(y,x);
}
int solve(int i,int op){
    while(!q.empty()) vis[q.back()]=inq[col[q.back()]]=0,q.pop_back(); 
    for(int x:vt[i]) q.epb(x);
    int rt=q.front(),nw=0; vis[rt]=1; inq[i]=1;
    //printf("visbg %d %d\n",rt,col[rt]);
    for(rg int l=1;l<q.size();++l){
        int x=q[l]; 
        if(vis[x]) continue;
        vis[x]=1;
        //printf("vis %d %d\n",x,col[x]);
        while(x!=rt){
            if(dep[rt]>dep[x]){
                rt=fa[rt];
                if(vis[rt]) break;
                vis[rt]=1;
                if(inq[col[rt]]) continue;
                ++nw; inq[col[rt]]=1;
                for(int y:vt[col[rt]]){
                    q.epb(y);
                    if(op&&q.size()>200) return q.epb(rt),k+1;
                }
            }else{
                x=fa[x];
                if(vis[x]) break;
                vis[x]=1;
                if(inq[col[x]]) continue;
                ++nw; inq[col[x]]=1;
                for(int y:vt[col[x]]){
                    q.epb(y);
                    if(op&&q.size()>200) return q.epb(x),k+1;
                }
            }
        }
    }
    used[i]=1;
    return nw;
}
signed main(){
    n=read(),k=read();
    rep(i,n-1){
        const int u=read(),v=read();
        e[u].epb(v),e[v].epb(u);
    }
    dfs(1,0);
    rep(i,n) col[i]=read(),vt[col[i]].epb(i),ord[i]=i;
    int ans(k+1);
    rep(i,k){
        if(!vt[i].size()){
            used[i]=1;
            continue;
        }
        if(vt[i].size()>200) continue;
        ans=min(ans,solve(i,1));
    }
    //puts("done");
    rep(i,k) tot+=(!used[i]);
    tot=min(tot,50);
    shuffle(ord+1,ord+1+n,rnd);
    for(rg int i=1;tot;++i){
        if(used[col[ord[i]]]) continue;
        --tot;
        ans=min(ans,solve(col[ord[i]],0));
    }
    printf("%d\n",ans);
    return 0;
}