P7215 [JOISC2020] 首都 题解

题意：

一个树上每个点有一个颜色，每次操作可以把所有颜色为 $i$ 的点变成另一个你指定的 $j$，问最少需要多少次操作可以使有一种颜色 $C$ 的所有点两两之间的路径上的点的颜色均为 $C$。

可以想到，答案实际上是选择的城市数量减去 $1$。

法一：倍增。

考虑对各个颜色建立满足如下性质的图 $G$：

如果颜色 $i$ 的虚树上有颜色 $j$ 的点，$i\to j$ 连一条边。

若能够得到 $G$，建出图后缩强联通分量，出度为 $0$ 且点数最小的分量就是答案。

用倍增或者树链剖分优化这个建图即可做到 $O(n\log n)$。

法二：点分治。

我们发现，如果一个城市的一个点被选，则该城市其他点也都必须被选，可以考虑用点分治来解，每次强制选分治中心，求选它的答案。

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

选它的答案可以用 bfs 实现：

维护一个队列，一开始加入分治重心的颜色到队列里，每次取队列头的颜色，枚举这个颜色的所有点 $x$，开始跳父亲，把路过的颜色加入队列，直到跳到一个已经在虚树上的点。

注意是只在分治子树内 bfs，因为如果出去了（队列为空且不存在队列中一种颜色不在当前分治树块内），就说明要经过更高的分治重心，那么在那个时候就统计答案了。

剩下就是注意点分治回收的时候的效率即可。

这个复杂度也是 $O(n\log n)$，常数更小。

倍增 code:

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

typedef long long LL;
typedef unsigned int ui;

const int N=2e5+5;

int n,k,clk,scc,ans;
int dfn[N],c[N],mn[N],rr[N],idfn[N],f[N],low[N],st[N],tp,sz[N],bel[N];
bool ins[N],ban[N];
vector<int> e[N],v[N];

inline void ckmin(int &x,int y) {
    y < x ? x= y : 0;}

inline void dfs(int x) {
    
	idfn[dfn[x]=++clk]=x;
	for(ui i=0,y; i<e[x].size(); i++)
		if(!dfn[y=e[x][i]]) f[y]=x,dfs(y);
	rr[x]=clk;
}

inline void tarjan(int x) {
    
	dfn[x]=low[x]=++clk;
	st[++tp]=x;
	ins[x]=1;
	for(ui i=0,y; i<v[x].size(); i++)
		if(!dfn[y=v[x][i]]) tarjan(y),ckmin(low[x],low[y]);
		else if(ins[y]) ckmin(low[x],dfn[y]);
	if(dfn[x]==low[x]) {
    
		int y;
		scc++;
		do {
    
			y=st[tp--];
			ins[y]=0;
			bel[y]=scc;
			sz[scc]++;
		} while(y!=x);
	}
}

int main() {
    
    scanf("%d%d",&n,&k); ans=k;
	for(int i=1; i<n; i++) {
    
		int x,y;
        scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1);
	memset(mn,0x3f,sizeof(mn));
	for(int i=1; i<=n; i++) {
    
		scanf("%d",&c[i]);
		ckmin(mn[c[i]],dfn[i]);
	}
	for(int i=1; i<=n; i++)
		if(dfn[i]>rr[idfn[mn[c[i]]]])
			mn[c[i]]=0;
	for(int i=1; i<=n; i++)
		if(dfn[i]^mn[c[i]])
			v[c[i]].push_back(c[f[i]]);
	memset(dfn,0,sizeof(dfn));
	clk=0;
	for(int i=1; i<=k; i++)
		if(!dfn[i]) tarjan(i);
	for(int i=1; i<=k; i++)
		for(ui j=0; j<v[i].size(); j++)
			if(bel[i]^bel[v[i][j]])
				ban[bel[i]]=1;
	for(int i=1; i<=scc; i++)
		if(!ban[i]) ans=min(ans,sz[i]);
	printf("%d\n",ans-1);
	return 0;
}

点分治 code:

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

typedef pair<int,int>P;
typedef unsigned int ui;
#define SZ 500005
#define CNUM 500005
#define INF 1000000000

int n,k,col[SZ];
vector<int>edge[SZ];
vector<int>vertex[CNUM];
bool rem[SZ];
int sub_size[SZ];
int ans = 1000000000;
bool check_col[CNUM];
int up[SZ];
vector<int>cur_vertex, cur_list[CNUM];

inline int make(int v,int u) {
    
	int cnt = 1;
	up[v] = u;
	check_col[col[v]] = 0;
	cur_vertex.push_back(v);
	cur_list[col[v]].clear();
	for(ui i=0; i<edge[v].size(); i++) {
    
		int to = edge[v][i];
		if(rem[to] || to == u) continue;
		cnt += make(to,v);
	}
	return sub_size[v] = cnt;
}

inline P search(int v,int u,int cur_size) {
    
	P ret = P(1000000000,-1);
	int sum=1,mx=0;
	for(ui i=0; i<edge[v].size(); i++) {
    
		int to = edge[v][i];
		if(rem[to] || to == u) continue;
		ret = min(ret,search(to,v,cur_size));
		mx = max(mx,sub_size[to]);
		sum += sub_size[to];
	}
	mx = max(mx,cur_size-sum);
	ret = min(ret,P(mx,v));
	return ret;
}

inline void sol(int v) {
    
	make(v,-1);
	cur_vertex.clear();
	int cent = search(v,-1,sub_size[v]).second;
	make(cent,-1);
	rem[cent] = true;
	int sz = cur_vertex.size();
	for(int i=0; i<sz; i++) cur_list[col[cur_vertex[i]]].push_back(cur_vertex[i]);
	queue<int>que;
	que.push(col[cent]);
	check_col[col[cent]] = 1;
	int use = 0;
	while(!que.empty()) {
    
		int c = que.front();
		que.pop();
		use++;
		if(cur_list[c].size() != vertex[c].size()) {
    
			use = INF;
			break;
		}
		for(ui i=0; i<cur_list[c].size(); i++) {
    
			int look = cur_list[c][i];
			if(up[look] == -1) continue;
			int nw = col[up[look]];
			if(!check_col[nw]) {
    
				que.push(nw);
				check_col[nw] = 1;
			}
		}
	}
	ans = min(ans,use);
	for(ui i=0; i<edge[cent].size(); i++) {
    
		if(!rem[edge[cent][i]]) sol(edge[cent][i]);
	}
	rem[cent] = false;
}

int main() {
    
	scanf("%d %d",&n,&k);
	for(int i=1; i<n; i++) {
    
		int a,b;
		scanf("%d%d",&a,&b);
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	for(int i=1; i<=n; i++) {
    
		scanf("%d",&col[i]);
		vertex[col[i]].push_back(i);
	}
	sol(1);
	assert(ans <= n);
	printf("%d\n",ans-1);
	return 0;
}