(mathcal{Description})
给定一个含 (n) 个点 (m) 条边的简单无向图，设图中最大点双的大小为 (s)，则保证 (sle6)。你将要用 (k) 种颜色为结点染色，其中有些结点需要染成的颜色被确定，其余结点颜色任意。一次染色可以将一块全部无色的连通块染成某种颜色。求最少染色次数。
(nle10^5)，(kle20)，(sle6)。
(mathcal{Solution})
提到点双，尝试建出广义圆方树，在其上 DP。
令 (f(u,c)) 表示圆点 (u) 或方点 (u) 的祖先的颜色为 (c) 时，染好 (u) 子树的最少操作次数。对于不定颜色的圆点 (u)，显然有
[f(u,c)=1+sum_{vinoperatorname{son}(u)}f(v,c)-1
]
即，在方儿子的位置钦定自己的颜色，自己所在的连通块可以一起合并。
接下来考虑方点 (u) 的转移。设 (u) 所代表的极大点双为 (C={v_0,v_1,cdots,v_k})，其中 (v_0) 为 (u) 在圆方树上的父亲。对于每个 (Ssubseteq C)，预处理出 (operatorname{con}(S)) 表示点集 (S) 的导出子图是否连通，即
[operatorname{con}(S)=egin{cases}mathrm{True}&|S|le1\igvee_{vin S}operatorname{con}(Ssetminus{v})land ((Ssetminus{v})capoperatorname{adj}(v)
ot=varnothing)& ext{otherwise}end{cases}
]
再令 (g(S,c)) 表示将 (C) 的连通子集 (S) 作为一个 (c) 颜色连通块时，将 (vin S) 及 (v) 的子树们染色的最少操作次数。类似于圆点转移，有
[g(S,c)=1+sum_{vin S}f(v,c)-1
]
顺带令 (G(S)=min{g(S,c)})，在此基础上，令 (h(S)) 表示将 (S) 分为若干个连通块时，将 (vin S) 及 (v) 的子树们染色的最少操作次数，就有
[h(S)=min_{Tsubsetneq S}{h(T)+G(Ssetminus T)}
]
最终，枚举 (v_0) 所在连通块，得到转移
[f(u,c)=min_{v_0in Ssubseteq C}{g(S,c)+G(Csetminus S)}
]
复杂度为 (mathcal O(n(3^s+k2^s)))。
(mathcal{Code})
/* Clearink */
#include <cstdio>
#include <cstring>
#include <unordered_set>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
inline int rint() {
int x = 0, s = getchar();
for ( ; s < '0' || '9' < s; s = getchar() );
for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );
return x;
}
inline void chkmin( int& a, const int b ) { b < a && ( a = b ); }
const int MAXN = 1e5, MAXM = 6e5, MAXK = 20, INF = 1000000;
int n, m, K, s, clr[MAXN + 5], vnode;
template<const int NODE, const int EDGE>
struct Graph {
int ecnt, head[NODE], to[EDGE], nxt[EDGE];
inline void operator () ( const int s, const int t ) {
#ifdef RYBY
printf( "%d %d
", s, t );
#endif
to[++ecnt] = t, nxt[ecnt] = head[s], head[s] = ecnt;
}
};
#define adj( g, u, v )
for ( int e = g.head[u], v; v = g.to[e], e; e = g.nxt[e] )
Graph<MAXN + 5, MAXM * 2 + 5> src;
Graph<MAXN * 2 + 5, MAXN * 2 + 5> cac;
std::unordered_set<int> adm[MAXN + 5];
inline void buildCactus( const int u, const int fa ) {
static int dfc, top, dfn[MAXN + 5], low[MAXN + 5], stk[MAXN + 5];
dfn[u] = low[u] = ++dfc, stk[++top] = u;
adj ( src, u, v ) if ( v != fa ) {
if ( !dfn[v] ) {
buildCactus( v, u ), chkmin( low[u], low[v] );
if ( low[v] >= dfn[u] ) {
cac( u, ++vnode );
do cac( vnode, stk[top] ); while ( stk[top--] != v );
}
} else chkmin( low[u], dfn[v] );
}
}
int f[MAXN * 2 + 5][MAXK + 5];
inline void solve( const int u, const int fa ) {
adj ( cac, u, v ) solve( v, u );
if ( u <= n ) {
if ( clr[u] ) {
rep ( i, 1, K ) f[u][i] = INF;
f[u][clr[u]] = 1;
adj ( cac, u, v ) f[u][clr[u]] += f[v][clr[u]] - 1;
} else {
rep ( i, 1, K ) f[u][i] = 1;
adj ( cac, u, v ) rep ( i, 1, K ) f[u][i] += f[v][i] - 1;
}
} else {
static bool con[100];
static int id[MAXN * 2 + 5], bitw[100], vec[10], ads[10];
static int g[100][MAXK + 5], h[100];
if ( !id[0] ) { // once.
memset( id, 0xff, sizeof id );
rep ( i, 2, 1 << 6 ) bitw[i] = bitw[i >> 1] + 1;
}
id[0] = vec[9] = 1, id[fa] = 0, vec[0] = fa;
adj ( cac, u, v ) id[v] = id[0]++, vec[vec[9]++] = v;
rep ( i, 0, vec[9] - 1 ) {
ads[i] = 0;
rep ( j, 0, vec[9] - 1 ) {
ads[i] |= int( i == j || adm[vec[i]].count( vec[j] ) ) << j;
}
}
rep ( S, 1, ( 1 << vec[9] ) - 1 ) {
if ( !S || !( S & ( S - 1 ) ) ) con[S] = true;
else {
con[S] = false;
rep ( v, 0, vec[9] - 1 ) if ( S >> v & 1 ) {
con[S] = con[S ^ ( 1 << v )]
&& ( ads[v] & ( S ^ ( 1 << v ) ) );
if ( con[S] ) break;
}
}
rep ( i, 1, K ) {
if ( !con[S] ) g[S][i] = INF;
else {
g[S][i] = 1;
rep ( j, 1, vec[9] - 1 ) if ( S >> j & 1 ) {
g[S][i] += f[vec[j]][i] - 1;
}
}
}
}
rep ( S, 0, ( 1 << vec[9] ) - 1 ) {
g[S][0] = INF;
rep ( i, 1, K ) {
chkmin( g[S][0], g[S][i] );
}
}
h[0] = 0;
rep ( S, 1, ( 1 << vec[9] ) - 1 ) {
h[S] = INF;
for ( int T = S; T; T = ( T - 1 ) & S ) {
chkmin( h[S], h[S ^ T] + g[T][0] );
}
}
rep ( i, 1, K ) {
f[u][i] = INF;
for ( int S = 1; S < 1 << vec[9]; S += 2 ) {
chkmin( f[u][i], g[S][i] + h[( ( 1 << vec[9] ) - 1 ) ^ S] );
}
}
}
// printf( "node %d:
", u );
// rep ( i, 1, K ) printf( "%d%c", f[u][i], i < K ? ' ' : '
' );
}
int main() {
freopen( "colorful.in", "r", stdin );
freopen( "colorful.out", "w", stdout );
n = rint(), m = rint(), K = rint(), s = rint();
rep ( i, 1, n ) clr[i] = rint();
rep ( i, 1, m ) {
int u = rint(), v = rint();
src( u, v ), src( v, u );
adm[u].insert( v ), adm[v].insert( u );
}
#ifdef RYBY
puts( "+++ +++ +++" );
#endif
vnode = n, buildCactus( 1, 0 );
#ifdef RYBY
puts( "--- --- ---" );
#endif
solve( 1, 0 );
int ans = INF;
rep ( i, 1, K ) chkmin( ans, f[1][i] );
printf( "%d
", ans );
return 0;
}