首都城市[JOISC 2020 Day4]

发表于 分类于

题目大意

一棵 $n$ 个节点的树，点有 $k$ 种颜色。

现在要求选出最小的颜色集合，使得在颜色集合中的点形成一个连通块。输出该集合的大小。

$n,k\leq 10^5$

题解

做法1

一个显然的 $O(k^2)$ 做法是将颜色当成点，如果选了某个颜色 $i$ 之后必须选颜色 $j$，则 $i$ 向 $j$ 连一条有向边。

然后跑Tarjan缩点，答案就是缩点后的图中出度为 $0$ 的点的 $size-1$ 的最小值。

对于每种颜色，我们发现，它要连出去的颜色显然是对该颜色的点建虚树后，在虚树中的节点颜色。

然后就可以用树上倍增来优化一下建图。发现你这样建图还是会满足和原图的强联通分量的形状是相同的。这样建完之后再一样的跑Tarjan即可。

做法2

一个点分治神仙做法，并不太会。

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

程序

做法1

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl;
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=200010;
const int M=10000010;
int n,k,cnt,col[N];
namespace Graph{
	int ver[M],ne[M],tot,head[M];
	int dfn[M],low[M],tim,sum[M];
	int st[M],top,bel[M],scc_cnt;
	bool in[M],bo[M];
	inline void add(int x,int y)
	{
		ver[++tot]=y; ne[tot]=head[x]; head[x]=tot;
	}
	void dfs(int u,int pre)
	{
		dfn[u]=low[u]=++tim;
		in[u]=1; st[++top]=u;
		for(int i=head[u],v;i;i=ne[i])
		{
			v=ver[i];
			if(!dfn[v])
			{
				dfs(v,u);
				low[u]=min(low[u],low[v]);
			}
			else if(in[v]) low[u]=min(low[u],dfn[v]);
		}
		if(low[u]==dfn[u])
		{
			int v;
			++scc_cnt;
			do
			{
				v=st[top--]; in[v]=0;
				bel[v]=scc_cnt;
			}while(v!=u);
		}
	}
	inline void tarjan()
	{
		fo(i,1,cnt) if(!dfn[i]) dfs(i,0);
	}
	inline void solve()
	{
		fo(u,1,cnt)
			for(int i=head[u];i;i=ne[i])
				if(bel[u]!=bel[ver[i]])
					bo[bel[u]]=1;
		fo(i,1,k) sum[bel[i]]++;
		int ans=k;
		fo(i,1,scc_cnt) if(!bo[i]) ans=min(ans,sum[i]-1);
		printf("%d\n",ans);
	}
	inline void work()
	{
		tarjan();
		solve();
	}
}
namespace Tree{
	vector<int> v[N];
	vector<int> adj[N];
	int tim,dfn[N],dep[N];
	int f[N][19],id[N][19];
	inline void add(int x,int y)
	{
		adj[x].pb(y); adj[y].pb(x);
	}
	void dfs(int u,int pre)
	{
		dep[u]=dep[pre]+1; dfn[u]=++tim;
		f[u][0]=pre;
		id[u][0]=++cnt;
		Graph::add(id[u][0],col[u]);
		for(int i=1;f[u][i]=f[f[u][i-1]][i-1];i++)
		{
			id[u][i]=++cnt;
			Graph::add(id[u][i],id[u][i-1]);
			Graph::add(id[u][i],id[f[u][i-1]][i-1]);
		}
		for(auto v:adj[u]) if(v!=pre) dfs(v,u);
	}
	inline int lca(int x,int y)
	{
		if(dep[x]>dep[y]) swap(x,y);
		fd(i,18,0) if(dep[f[y][i]]>=dep[x]) y=f[y][i];
		if(x==y) return x;
		fd(i,18,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
		return f[x][0];
	}
	inline void Gadd(int col,int x,int y)
	{
		int z=lca(x,y);
		Graph::add(col,id[z][0]);
		fd(i,18,0)
		{
			if(f[x][i]&&dep[f[x][i]]>=dep[z])
			{
				Graph::add(col,id[x][i]);
				x=f[x][i];
			}
			if(f[y][i]&&dep[f[y][i]]>dep[z])
			{
				Graph::add(col,id[y][i]);
				//DEBUG(i);
				y=f[y][i];
			}
		}
	}
	inline void solve()
	{
		fo(i,1,k)
		{
			sort(all(v[i]),[&](const int &x,const int &y){return dfn[x]<dfn[y];});
			//DEBUG(v[i].size());
			if(!v[i].size()) continue;
			v[i].pb(v[i][0]);
			fo(j,0,v[i].size()-2) Gadd(i,v[i][j],v[i][j+1]);
		}
	}
}
int main()
{
	n=read(); k=read(); cnt=k;
	fo(i,2,n) Tree::add(read(),read());
	fo(i,1,n) Tree::v[col[i]=read()].pb(i);
	Tree::dfs(1,0);
	Tree::solve();
	Graph::work();
	return 0;
}