「JOISC 2020 Day4」首都城市

题目大意：给定一棵树，每个点有颜色

求选择一个最小的颜色集合，使得这些颜色的点能够构成一个连通块

容易发现，选取这个颜色就必须将这个颜色连通路径上的所有其它颜色选掉

但是要纠正一个：

并不是选取的这个颜色的连通路径上的颜色就行

因为选取另一个颜色，可能导致不在当前连通路径上的其它颜色也需要被选取

这样的关系构成一个有向图，一条边表示选了$u$就选$v$

因此可以考虑$\text{tarjan}$强连通缩点，由于最终我们选择强连通分量一定没有出边（否则不优）

因此可以线性统计答案，问题在于如何建立这个图

首先考虑如何将这个连通路径提取出来，一种简单的办法是：找到这个颜色所有点的$\text{LCA}$，路径就可以表示为$\text{LCA}$到所有点路径的并

Solution1

树剖线段树完成路径连边

点数为$O(n)$，边数为$O(n\log ^2n)$

Solution2

倍增连边

点数边数均为$O(n\log n)$

Solution3

离线，用类似$\text{tarjan LCA}$的方式，维护一个并查集

每次并查集的父亲关系改变时，新建节点，即可完成一个类似可持久化的操作

如果再用$\text{tarjan}$预处理$\text{LCA}$，复杂度/点数/边数 就为$O(n\alpha(n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> Pii;
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
char buf[200000],*p1,*p2;
#define getchar() (((p1==p2)&&(p2=(p1=buf)+fread(buf,1,200000,stdin))),*p1++)
int rd(){
	int s=0;static char c;
	while(c=getchar(),c<48);
	do s=(s<<1)+(s<<3)+(c^'0');
	while(c=getchar(),c>47);
	return s;
}

const int N=2e5+10,INF=1e9+10,K=N*3.5;

int n,k,m;
int A[N],L[N],F[N],C[N],Fir[N],I[N];
vector <int> G[N],V[N];
struct Edge{ 
	int to,nxt; 
} e[K*2];
int head[K],ecnt;
void AddEdge(int u,int v){
	if(u==v) return;
	e[++ecnt]=(Edge){v,head[u]};
	head[u]=ecnt;
}

int Find1(int x){ return F[x]==x?x:F[x]=Find1(F[x]); }
void pre_dfs(int u,int f){
	F[u]=u;
	if(!Fir[A[u]]) Fir[A[u]]=u;
	if(--C[A[u]]==0) L[A[u]]=Find1(Fir[A[u]]);
	for(int v:G[u]) if(v!=f) pre_dfs(v,u);
	F[u]=f;
}

Pii Find(int x){
	if(F[x]==x) return mp(F[x],I[x]);
	Pii t=Find(F[x]);
	return AddEdge(++m,t.second),AddEdge(m,I[x]),F[x]=t.first,mp(F[x],I[x]=m);
}

void dfs(int u,int f){
	F[u]=u,I[u]=A[u];
	for(int v:G[u]) if(v!=f) dfs(v,u);
	for(int v:V[u]) AddEdge(A[v],Find(v).second);
	F[u]=f;
}

int t[K],low[K],ins[K],stk[K],top,dfn;
int ans=1e9,vis[N],out[K];
void dfs(int u){
	t[u]=low[u]=++dfn,ins[stk[++top]=u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!t[v]) dfs(v),cmin(low[u],low[v]);
		else if(ins[v]) cmin(low[u],t[v]);
	}
	if(low[u]==t[u]){
		int fl=1,tmp=top;
		for(int v=-1;v!=u;){
			v=stk[top--];
			for(int i=head[v];i;i=e[i].nxt) if(!ins[e[i].to]) { fl=0; break; }
		}
		rep(i,top+1,tmp) ins[stk[i]]=0;
		if(fl) {
			int res=0;
			rep(i,top+1,tmp) {
				int x=stk[i];
				if(x<=k && !vis[x]) vis[x]=1,res++;
			}
			rep(i,top+1,tmp) if(stk[i]<=k) vis[stk[i]]=0;
			if(res) cmin(ans,res-1);
		}
	}
}

int main(){
	n=rd(),k=rd();
	rep(i,2,n) {
		int u=rd(),v=rd();
		G[u].pb(v),G[v].pb(u);
	}
	rep(i,1,n) C[A[i]=rd()]++;
	pre_dfs(1,0);
	rep(i,1,n) V[L[A[i]]].pb(i);
	m=k;
	dfs(1,0);
	rep(i,1,k) if(!t[i]) dfs(i);
	printf("%d\n",ans);
	fprintf(stderr,"Vertices =%d \nEdges =%d\n",m,ecnt);
}