P7215 JOISC2020 首都

点分治好题。

思路

求出当前分治中心，把当前分治中心作为首都，暴力跑需要合并多少个城市，不能越过上一层分治中心。

如果越过了上一个分治中心，把上一个分治中心作为首都也可以起到相同的效果，就没有必要再跑一次了。

时间复杂度 \(O(n\log n)\)。

CODE

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;

struct Edge
{
    int tot;
    int head[maxn];
    struct edgenode{int to,nxt;}edge[maxn*2];
    inline void add(int x,int y)
    {
        tot++;
        edge[tot].to=y;
        edge[tot].nxt=head[x];
        head[x]=tot;
    }
}T;

int n,ans;
int col[maxn],fa[maxn],bol[maxn];

vector<int>vec[maxn];

int siz[maxn];
bool cut[maxn],book[maxn],vis[maxn];
inline void dfs_siz(int u)
{
    book[u]=true;siz[u]=1;
    for(int i=T.head[u];i;i=T.edge[i].nxt)
    {
        int v=T.edge[i].to;
        if(book[v]||cut[v]) continue;
        dfs_siz(v);siz[u]+=siz[v];
    }
    book[u]=false;
}
inline int dfs_rt(int u,const int tot)
{
    book[u]=true;int ret=u;
    for(int i=T.head[u];i;i=T.edge[i].nxt)
    {
        int v=T.edge[i].to;
        if(book[v]||cut[v]) continue;
        if(siz[v]*2>=tot){ret=dfs_rt(v,tot);break;}
    }
    book[u]=false;return ret;
}
int cnt;
inline void bfs(int g)
{
    queue<int>que;
    for(auto v:vec[col[g]])
    {
        que.push(v),vis[v]=true;
        if(bol[v]!=g) {cnt=n;return ;}
    }
    while(!que.empty())
    {
        int u=que.front();que.pop();
        if(vis[fa[u]]) continue;
        for(auto v:vec[col[fa[u]]])
        {
            que.push(v),vis[v]=true;
            if(bol[v]!=g) {cnt=n;return ;}
        }
        cnt++;
    }
}
inline void dfs2(int u,const int g)
{
    book[u]=true;vis[u]=false;bol[u]=g;
    for(int i=T.head[u];i;i=T.edge[i].nxt)
    {
        int v=T.edge[i].to;
        if(book[v]||cut[v]) continue;
        fa[v]=u;
        dfs2(v,g);
    }
    book[u]=false;
}
inline void dfs(int u)
{
    dfs_siz(u);int g=dfs_rt(u,siz[u]);cut[g]=true;
    fa[g]=g;dfs2(g,g);cnt=0;bfs(g);ans=min(ans,cnt);
    for(int i=T.head[g];i;i=T.edge[i].nxt)
    {
        int v=T.edge[i].to;
        if(cut[v]) continue;
        dfs(v);
    }
}

int main()
{
    scanf("%d%d",&n,&ans);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        T.add(u,v),T.add(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&col[i]);
        vec[col[i]].emplace_back(i);
    }
    dfs(1);
    printf("%d",ans);
}