题目
点这里看题目。
分析
做法比较容易看出来。我们对于每个城市，找出那些 " 如果这个城市在首都内，则必须在首都内的其它城市 " ，也就是为了让这个城市的小镇连通而必须选的城市。
接着，我们新建一个有向图，将一个城市看成一个点，一条边$(u,v)$代表 " $u$在首都则$v$必在首都 " ，即上文所说的关系。对这个图进行强连通分量分解。假想我们对这个图缩点。缩点后的图上，一个点如果被选在首都内，它所能到达的点都必须选在首都内，我们称选定它的代价为它所能到达的城市的个数（注意这里说的是城市，即未缩点的图上的点）。因此最优策略一定会选定一个没有出度的点，答案即是没有出度的点中的最小代价。
强连通分量分解可以用 Tarjan ，时间是线性的；而前面的有向图可能会被卡到$O(n^2)$，因此我们考虑优化建这个有向图。
瓶颈在于如何确定哪些城市是必须选的。对于树上多个颜色的情况，我们一般会想到用虚树。因此，我们就对于每一个城市，建起它的虚树。可以发现，虚树上的小镇一定会被选定，它们所属的城市一定会被选定。因此，对于每一个小镇，它到它所在城市的虚树的根上的所有小镇都是必选的。这是一个树上路径覆盖情况，我们可以用倍增优化建图。
具体而言，我们对每个城市建立一个点；让每个小镇向它所在的城市连一条边；构造倍增辅助图；对于每个小镇，让它所在的城市连到上文所说的路径对应的辅助点上（类似 RMQ 的 ST 表，这里连接的辅助点所对应的小镇可以重复，但不能遗漏），可以发现每次最多连两个辅助点。
这样的图的点是$O(nlog_2n)$，边是$O(nlog_2n)$。然后跑 Tarjan 计算答案即可。
代码
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 2e5 + 5, MAXLOG = 20, MAXS = MAXN * MAXLOG;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
struct edge
{
int to, nxt;
}Graph[MAXS << 1];
vector<int> G[MAXN], town[MAXN], SCC[MAXS];
int siz[MAXS], deg[MAXS];
int head[MAXS], DFN[MAXS], LOW[MAXS], bel[MAXS], sta[MAXS];
int f[MAXN][MAXLOG], id[MAXN][MAXLOG];
int c[MAXN], dep[MAXN], pos[MAXN];
int N, K, lg2, ID, tot, top, cnt;
bool inSta[MAXS];
void addEdge( const int from, const int to )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
head[from] = cnt;
}
void DFS( const int u, const int fa )
{
f[u][0] = fa;
if( f[u][0] ) id[u][0] = ++ tot, addEdge( tot, fa ), addEdge( tot, u );
dep[u] = dep[fa] + 1, pos[u] = ++ ID;
for( int i = 0, v ; i < G[u].size() ; i ++ )
if( ( v = G[u][i] ) ^ fa )
DFS( v, u );
}
void init()
{
lg2 = log2( N );
for( int j = 1 ; j <= lg2 ; j ++ )
for( int i = 1 ; i <= N ; i ++ )
{
f[i][j] = f[f[i][j - 1]][j - 1];
if( ! f[i][j] ) continue; id[i][j] = ++ tot;
addEdge( id[i][j], id[i][j - 1] ), addEdge( id[i][j], id[f[i][j - 1]][j - 1] );
}
}
void balance( int &u, const int s ) { for( int i = 0 ; ( 1 << i ) <= s ; i ++ ) if( s & ( 1 << i ) ) u = f[u][i]; }
void cover( int u, int s )
{
if( ! s ) return ;
int k = log2( s ), col = c[u] + N;
addEdge( col, id[u][k] );
if( ! ( s -= 1 << k ) ) return ;
balance( u, s ), addEdge( col, id[u][k] );
}
int LCA( int u, int v )
{
if( dep[u] > dep[v] ) balance( u, dep[u] - dep[v] );
if( dep[v] > dep[u] ) balance( v, dep[v] - dep[u] );
if( u == v ) return u;
for( int i = lg2 ; ~ i ; i -- ) if( f[u][i] ^ f[v][i] ) u = f[u][i], v = f[v][i];
return f[u][0];
}
void Tarjan( const int u )
{
DFN[u] = LOW[u] = ++ ID;
inSta[sta[++ top] = u] = true;
for( int i = head[u], v ; i ; i = Graph[i].nxt )
{
if( ! DFN[v = Graph[i].to] ) Tarjan( v ), LOW[u] = MIN( LOW[u], LOW[v] );
else if( inSta[v] ) LOW[u] = MIN( LOW[u], DFN[v] );
}
if( LOW[u] == DFN[u] )
{
int v; tot ++;
do inSta[v = sta[top --]] = false, SCC[bel[v] = tot].push_back( v ); while( v ^ u );
}
}
int main()
{
read( N ), read( K ); tot = N + K;
for( int i = 1, a, b ; i < N ; i ++ ) read( a ), read( b ), G[a].push_back( b ), G[b].push_back( a );
for( int i = 1 ; i <= N ; i ++ ) read( c[i] ), town[c[i]].push_back( i ), addEdge( i, c[i] + N );
DFS( 1, 0 );
init();
for( int i = 1 ; i <= K ; i ++ )
{
int mn = town[i][0], mx = town[i][0];
for( int u, j = 1 ; j < town[i].size() ; j ++ )
{
u = town[i][j];
if( pos[u] < pos[mn] ) mn = u;
if( pos[u] > pos[mx] ) mx = u;
}
int lca = LCA( mx, mn );
for( int j = 0 ; j < town[i].size() ; j ++ )
cover( town[i][j], dep[town[i][j]] - dep[lca] );
}
int up = tot; tot = ID = 0;
for( int i = 1 ; i <= up ; i ++ )
if( ! DFN[i] )
Tarjan( i );
for( int i = 1 ; i <= tot ; i ++ )
for( int j = 0 ; j < SCC[i].size() ; j ++ )
if( N < SCC[i][j] && SCC[i][j] <= N + K )
siz[i] ++;
int ans = N;
for( int i = 1 ; i <= tot ; i ++ )
for( int j = 0 ; j < SCC[i].size() ; j ++ )
for( int k = head[SCC[i][j]] ; k ; k = Graph[k].nxt )
if( bel[Graph[k].to] ^ i )
deg[i] ++;
for( int i = 1 ; i <= tot ; i ++ ) if( ! deg[i] ) ans = MIN( ans, siz[i] - 1 );
write( ans ), putchar( '
' );
return 0;
}