题目

分析

做法比较容易看出来。我们对于每个城市，找出那些 " 如果这个城市在首都内，则必须在首都内的其它城市 " ，也就是为了让这个城市的小镇连通而必须选的城市。

接着，我们新建一个有向图，将一个城市看成一个点，一条边\((u,v)\)代表 " \(u\)在首都则\(v\)必在首都 " ，即上文所说的关系。对这个图进行强连通分量分解。假想我们对这个图缩点。缩点后的图上，一个点如果被选在首都内，它所能到达的点都必须选在首都内，我们称选定它的代价为它所能到达的城市的个数（注意这里说的是城市，即未缩点的图上的点）。因此最优策略一定会选定一个没有出度的点，答案即是没有出度的点中的最小代价。

强连通分量分解可以用 Tarjan ，时间是线性的；而前面的有向图可能会被卡到\(O(n^2)\)，因此我们考虑优化建这个有向图。

瓶颈在于如何确定哪些城市是必须选的。对于树上多个颜色的情况，我们一般会想到用虚树。因此，我们就对于每一个城市，建起它的虚树。可以发现，虚树上的小镇一定会被选定，它们所属的城市一定会被选定。因此，对于每一个小镇，它到它所在城市的虚树的根上的所有小镇都是必选的。这是一个树上路径覆盖情况，我们可以用倍增优化建图。

具体而言，我们对每个城市建立一个点；让每个小镇向它所在的城市连一条边；构造倍增辅助图；对于每个小镇，让它所在的城市连到上文所说的路径对应的辅助点上（类似 RMQ 的 ST 表，这里连接的辅助点所对应的小镇可以重复，但不能遗漏），可以发现每次最多连两个辅助点。

这样的图的点是\(O(n\log_2n)\)，边是\(O(n\log_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( '\n' );

	return 0;

}

巴特西

「JOISC 2020 Day4」首都城市

题目

分析

代码

最新文章

热门文章