「题解」「JOISC2020」首都城市 Capital City

题目链接:LibreOJ 3280/JOISC2020 D4T1

题目

题目描述

原题 pdf

题目翻译

在 JOI 的国度有 $n$ 个小镇,从 $1$ 到 $n$ 编号,并由 $m$ 条双向道路连接。第 $m$ 条道路连接了 $A _ i$ 和 $B _ i$ 这两个编号的小镇。

这个国家的国王现将整个国家分为 $k$ 个城市,从 $1$ 到 $k$ 编号,每个城市都有附属的小镇,其中编号为 $j$ 的小镇属于编号为 $c _ j$ 的城市。每个城市至少有一个附属小镇。

国王还要选定一个首都。首都的条件是该城市的任意小镇都只能通过属于该城市的小镇到达。

但是现在可能不存在这样的选址,所以国王还需要将一些城市进行合并。对于合并城市 $x$ 和 $y$,指的是将所有属于 $y$ 的小镇划归给 $x$ 城。

你需要求出最少的合并次数。

数据范围

见原题 pdf。

时空限制

见原题 pdf。

题解

本题有多种做法。

解法 A(虚树 + 树上倍增 + Tarjan)

思路

我们不妨对于每一种颜色都建立一颗虚树,如果对于同为颜色 $i$ 的两个点,他们之间的路径经过了颜色为 $j$ 的点,我们可以连接一条 $j\to i$ 的边,意为 $i$ 要成为首都,需要把 $j$ 变为 $i$。

那么考虑新图上的情况:

  1. 存在一个点 $i$ 满足:不在一个环上。那么答案为 $0$,因为只要把 $i$ 设为首都即可。
  2. 存在环,环的大小为 $x$,那么答案为 $\min\{x-1\}$。只要把环上的点都合并即可。

答案现在很简单了,建立新图,求环即可。

需要用一些方法卡空间、加快速度,例如倍增建图。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}

const int MAXN=200000+5;
const int MAXLOG2N=18+1;
const int MAXK=200000+5;

int n,K;
vector<int> V[MAXK];
int tot;

namespace Graph{
    const int MAXV=5e6;
    vector<int> G[MAXV];
    inline void Add_Edge(reg int u,int v){
        G[u].push_back(v);
        return;
    }
    bool vis[MAXV];
    int tim,dfn[MAXV],low[MAXV];
    int top,S[MAXV];
    int Tarjan_cnt,color[MAXV];
    inline void Tarjan(reg int ID){
        vis[ID]=true;
        dfn[ID]=low[ID]=++tim;
        S[++top]=ID;
        for(reg int i=0,size=G[ID].size();i<size;++i){
            reg int to=G[ID][i];
            if(!dfn[to]){
                Tarjan(to);
                low[ID]=min(low[ID],low[to]);
            }
            else if(vis[to])
                low[ID]=min(low[ID],dfn[to]);
        }
        if(dfn[ID]==low[ID]){
            reg int To;
            ++Tarjan_cnt;
            do{
                To=S[top--];
                vis[To]=false;
                color[To]=Tarjan_cnt;
            }while(To!=ID);
        }
        return;
    }
    bool out[MAXV];
    int size[MAXV];
    inline void Solve(void){
        for(reg int i=1;i<=tot;++i)
            if(!dfn[i])
                Tarjan(i);
        for(reg int i=1;i<=tot;++i)
            if(!out[color[i]])
                for(reg int j=0,size=G[i].size();j<size;++j)
                    if(color[i]!=color[G[i][j]]){
                        out[color[i]]=true;
                        break;
                    }
        for(reg int i=1;i<=K;++i)
            ++size[color[i]];
        int ans=K-1;
        for(reg int i=1;i<=Tarjan_cnt;++i)
            if(!out[i])
                ans=min(ans,size[i]-1);
        printf("%d\n",ans);
        return;
    }
}

namespace Tree{
    vector<int> T[MAXN];
    inline void Add_Edge(reg int u,int v){
        T[u].push_back(v);
        return;
    }
    int fa[MAXN][MAXLOG2N],dep[MAXN];
    int tim,dfn[MAXN];
    int pos[MAXN][MAXLOG2N];
    inline void DFS(reg int ID,reg int father){
        dfn[ID]=++tim;
        fa[ID][0]=father;
        pos[ID][0]=++tot;
        dep[ID]=dep[father]+1;
        for(reg int i=1;(1<<i)<=dep[ID];++i){
            fa[ID][i]=fa[fa[ID][i-1]][i-1];
            pos[ID][i]=++tot;
            Graph::Add_Edge(pos[ID][i],pos[ID][i-1]);
            Graph::Add_Edge(pos[ID][i],pos[fa[ID][i-1]][i-1]);
        }
        for(reg int i=0,size=T[ID].size();i<size;++i){
            reg int to=T[ID][i];
            if(to!=father)
                DFS(to,ID);
        }
        return;
    }
    inline int LCA(int x,int y){
        if(dep[x]>dep[y])
            swap(x,y);
        for(reg int i=MAXLOG2N-1;i>=0;--i)
            if(dep[fa[y][i]]>=dep[x])
                y=fa[y][i];
        if(x==y)
            return x;
        for(reg int i=MAXLOG2N-1;i>=0;--i)
            if(fa[x][i]!=fa[y][i])
                x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
    inline void Add_Edge(reg int id,reg int x,reg int y){
        reg int lca=LCA(x,y);
        for(reg int i=MAXLOG2N-1;i>=0;--i){
            if(dep[fa[x][i]]>=dep[lca]){
                Graph::Add_Edge(id,pos[x][i]);
                x=fa[x][i];
            }
            if(dep[fa[y][i]]>=dep[lca]){
                Graph::Add_Edge(id,pos[y][i]);
                y=fa[y][i];
            }
        }
        Graph::Add_Edge(id,pos[lca][0]);
        return;
    }
    inline bool cmp(reg int a,reg int b){
        return dfn[a]<dfn[b];
    }
    inline void Solve(reg int id){
        if(V[id].size()){
            sort(V[id].begin(),V[id].end(),cmp);
            V[id].push_back(V[id][0]);
            for(reg int i=1,size=V[id].size();i<size;++i)
                Add_Edge(id,V[id][i-1],V[id][i]);
        }
        return;
    }
}

int main(void){
    n=read(),K=read();
    for(reg int i=1;i<n;++i){
        static int a,b;
        a=read(),b=read();
        Tree::Add_Edge(a,b);
        Tree::Add_Edge(b,a);
    }
    tot=K;
    Tree::DFS(1,0);
    for(int i=1;i<=n;++i){
        static int c;
        c=read();
        V[c].push_back(i);
        Graph::Add_Edge(Tree::pos[i][0],c);
    }
    for(reg int i=1;i<=K;++i)
        Tree::Solve(i);
    Graph::Solve();
    return 0;
}

解法 B(点分治)

思路

我们发现,如果一个城市的一个点被选,则该城市其他点也都必须被选,可以考虑用点分治来解。

假设当前分治到的重心为 $x$,则只需考虑必经 $x$ 的连通块即可。

我们可以维护一个队列,开始的时候将重心的颜色放入,然后对每一种颜色的所有节点进行扩展:向上跳父亲,直到被访问过。

如果队列为空且不存在队列中一种颜色不在当前分治树块内,则可以更新一下答案。

这种总时间复杂度为 $\Theta(n\log _ 2n)$,但运行时间比上面的做法更短,写起来也更简单。

代码

略。